文档介绍：实验题目: 查找技术综合应用实验目的: (1) 熟练掌握查找的常用算法; (2 )熟练设计和应用查找算法解决比较简单的实际问题。实验内容: 二叉排序树。任意给定一组数据, 设计一个算法, 建立一棵二叉排序树, 对它进行查找、插入、删除等操作。设计分析: 实验要求对建立的二叉排序树进行一系列的操作, 因此可以设置一个循环菜单, 对二叉排序树进行循环操作, 操作包括: 二叉排序树的创建, 结点的插入、查找、删除, 二叉排序树的重置,退出等。由于二叉排序树不同于一般的二叉树, 创建时即一个一个插入关键字, 若当前插入的关键字小于根结点上的关键字,则向其左子树进行递归插入操作,若大于根结点上的关键字, 则向右子树进行递归插入操作, 因此二叉排序树的中序遍历序列是一个有序的数列。由此创建好的二叉排序树在进行插入结点和查找结点操作也是这样进行。而进行删除操作时, 由此规则找到要删除的关键字时,删除后要对二叉排序树的相关结点重新排列。(1 ) 若待删除的结点是叶子节点,直接删除该结点; (2) 若待删除的结点只有左子树而无右子树,删除后将其左子树的根结点放在被删结点的位置; (3) 若待删除的结点只有右子树而无左子树,删除后将其右子树的根结点放在被删结点的位置; (4) 若待删除的结点同时有左子树和右子树,可以从其左子树中选择关键字最大的结点或从其右子树中选择关键字最小的结点放在被删去的结点的位置上。源程序代码: #include <> #include <> #define MAXV 30 typedef int KeyType; typedef struct node { KeyType key; struct node * lchild, * rchild; }BSTNode; BSTNode * BST; KeyType A[MAXV], flag=0; int InsertBST(BSTNode * &p, KeyType k) // 插入结点{ if (p==NULL) { p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=k; p->lchild=p->rchild=NULL; return 1; } else if (k==p->key) return 0; else if (k<p->key) return InsertBST(p->lchild, k); else return InsertBST(p->rchild, k); } BSTNode * CreatBST(KeyType A[], int n) // 创建二叉排序树{ BSTNode * bt= NULL; for (int i=0; i<n; i++) InsertBST(bt, A[i]); return bt; } void PrintBST(BSTNode * p) // 括号表示法输出二叉排序树{ if (p!=NULL) { printf("%d", p->key); if (p->lchild!=NULL||p->rchild!=NULL) { printf("("); PrintBST(p->lchild); if (p->rchild!=NULL) printf(","); PrintBST(p