东莞东城做网站公司,百度新闻头条,wordpress手机版侧栏导航栏,门户网站建设提案文章目录 1. 引言2. 二叉查找树3. 实验内容3.1 实验题目#xff08;一#xff09;输入要求#xff08;二#xff09;输出要求 3.2 算法实现1. 数据结构2. 全局变量3. 中序遍历函数InOrder4. 二叉查找树的构建函数T5. 主函数 3.3 代码整合 4. 实验结果 1. 引言 二叉查找树一输入要求二输出要求 3.2 算法实现1. 数据结构2. 全局变量3. 中序遍历函数InOrder4. 二叉查找树的构建函数T5. 主函数 3.3 代码整合 4. 实验结果 1. 引言 二叉查找树Binary Search TreeBST是一种常用的数据结构它在计算机科学和信息处理中有着广泛的应用。BST的特点是对于树中的每个节点其左子树的所有节点值小于当前节点的值而右子树的所有节点值大于当前节点的值。 本实验将通过C语言构建一个二叉查找树分析其性能计算平均查找长度。 2. 二叉查找树 二叉查找树Binary Search TreeBST是一种二叉树其中每个节点都包含一个键值key和对应的数据value。而且对于任意节点其左子树中的所有节点的键值都小于该节点的键值而右子树中的所有节点的键值都大于该节点的键值。 二叉查找树的这种特性使得在查找、插入和删除节点时具有高效性。通过比较目标键值和当前节点的键值可以在树中快速定位到目标节点或确定插入、删除的位置。在平均情况下这些操作的时间复杂度为O(log n)其中n是二叉查找树中节点的数量。 除了高效的查找操作二叉查找树还支持有序性操作。通过中序遍历二叉查找树可以按照键值的顺序输出树中的所有节点从而实现对节点的有序访问。 需要注意的是如果二叉查找树的节点插入和删除不平衡即树的高度不均衡地增长可能会导致查找、插入和删除操作的最坏情况时间复杂度为O(n)其中n是树中节点的数量。为了解决这个问题可以使用自平衡的二叉查找树如红黑树Red-Black Tree或AVL树来保持树的平衡性。
3. 实验内容
3.1 实验题目 实现教材 287 页底部的算法 T,从无到有创建一棵二叉查找树输出中根遍历序列并编程计算查找成功时的平均查找长度。
一输入要求 char *A[30]{THE,OF,AND,TO,A,IN,THAT,IS,WAS,HE,FOR,IT,WITH,AS,HIS,ON,BE,AT,BY,I,THIS,HAD,NOT,ARE,BUT,FROM,OR,HAVE,AN,THEY,};二输出要求
输出该二叉查找树的中根遍历序列输出该二叉查找树查找成功时的平均查找长度。
3.2 算法实现
1. 数据结构
typedef struct P {char *key;struct P* llink;struct P* rlink;
} P;2. 全局变量
P *root;
int Sum 0;3. 中序遍历函数InOrder
void InOrder(P *t)
{if(tNULL) return;else{InOrder(t-llink);printf(%s\n,t-key);InOrder(t-rlink);}
}递归地进行中序遍历输出节点的关键词。
4. 二叉查找树的构建函数T
P* T(char *ch) {if (root NULL) {root (P*)malloc(sizeof(P));root-key strdup(ch);root-llink NULL;root-rlink NULL;return NULL;}P* p root;while (p ! NULL) {Sum;if (strcmp(ch, p-key) 0)return p;if (strcmp(ch, p-key) 0) {if (p-llink NULL)break;elsep p-llink;}else {if (p-rlink NULL)break;elsep p-rlink;}}P* q (P*)malloc(sizeof(P));q-key strdup(ch);q-llink NULL;q-rlink NULL;if (strcmp(ch, p-key) 0)p-llink q;elsep-rlink q;return NULL;
}
若树为空直接创建根节点。若树不为空根据二叉查找树的性质找到合适的位置插入新的节点。
5. 主函数
int main() {char *A[30]{THE,OF,AND,TO,A,IN,THAT,IS,WAS,HE,FOR,IT,WITH,AS,HIS,ON,BE,AT,BY,I,THIS,HAD,NOT,ARE,BUT,FROM,OR,HAVE,AN,THEY,};int M 30, i;for (i 0; i M; i) {char *ch;ch A[i];P* s T(ch);}printf(中序遍历:\n);InOrder(root);Sum 0;for (i 0; i M; i) {char *ch;ch A[i];P* s T(ch);}printf(平均查找长度为%f, (float)Sum / M);// 释放节点的关键词内存for (i 0; i M; i) {free(A[i]);}return 0;
}
利用关键词数组 A 构建二叉查找树。输出中序遍历结果。再次构建二叉查找树计算平均查找长度并输出。
3.3 代码整合
#includestdio.h
#includestring.h
#includemalloc.htypedef struct P {char *key;struct P* llink;struct P* rlink;
} P;P *root;
int Sum 0;void InOrder(P *t) {if (t NULL)return;else {InOrder(t-llink);printf(%s\n, t-key);InOrder(t-rlink);}
}P* T(char *ch) {if (root NULL) {root (P*)malloc(sizeof(P));root-key strdup(ch);root-llink NULL;root-rlink NULL;return NULL;}P* p root;while (p ! NULL) {Sum;if (strcmp(ch, p-key) 0)return p;if (strcmp(ch, p-key) 0) {if (p-llink NULL)break;elsep p-llink;}else {if (p-rlink NULL)break;elsep p-rlink;}}P* q (P*)malloc(sizeof(P));q-key strdup(ch);q-llink NULL;q-rlink NULL;if (strcmp(ch, p-key) 0)p-llink q;elsep-rlink q;return NULL;
}int main() {char *A[30]{THE,OF,AND,TO,A,IN,THAT,IS,WAS,HE,FOR,IT,WITH,AS,HIS,ON,BE,AT,BY,I,THIS,HAD,NOT,ARE,BUT,FROM,OR,HAVE,AN,THEY,};int M 30, i;for (i 0; i M; i) {char *ch;ch A[i];P* s T(ch);}printf(中序遍历:\n);InOrder(root);Sum 0;for (i 0; i M; i) {char *ch;ch A[i];P* s T(ch);}printf(平均查找长度为%f, (float)Sum / M);// 释放节点的关键词内存for (i 0; i M; i) {free(A[i]);}return 0;
}
4. 实验结果 中序遍历:
A
AN
AND
ARE
AS
AT
BE
BUT
BY
FOR
FROM
HAD
HAVE
HE
HIS
I
IN
IS
IT
NOT
OF
ON
OR
THAT
THE
THEY
THIS
TO
WAS
WITH
平均查找长度为5.433333
