1. 引言

  二叉查找树（Binary Search Tree，BST）是一种常用的数据结构，它在计算机科学和信息处理中有着广泛的应用。BST的特点是对于树中的每个节点，其左子树的所有节点值小于当前节点的值，而右子树的所有节点值大于当前节点的值。

本实验将通过C语言构建一个二叉查找树，分析其性能计算平均查找长度。

2. 二叉查找树

  二叉查找树（Binary Search Tree，BST）是一种二叉树，其中每个节点都包含一个键值（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",};

（二）输出要求

1. 输出该二叉查找树的中根遍历序列；
2. 输出该二叉查找树查找成功时的平均查找长度。

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(t==NULL) 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 代码整合

#include<stdio.h>
#include<string.h>
#include<malloc.h>typedef 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