二叉搜索树实现与优化：课程设计解析

二叉排序树与平衡二叉排序树基本操作的实现50标签：排序,平衡,操作 
1.用二叉链表作存储结构 
(1)以回车('\n')为输入结束标志,输入数列L,生成二叉排序树T；
(2)对二叉排序树T作中序遍历,输出结果；
(3)计算二叉排序树T的平均查找长度,输出结果；
(4)输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无结点x”；
(5)判断二叉排序树T是否为平衡二叉树,输出信息“OK！”/“NO！”；
*(6)再用数列L,生成平衡二叉排序树BT:当插入新元素之后,发现当前的二叉排序树BT不是平衡二叉排序树,则立即将它转换成新的平衡二叉排序树BT； 
*(7)计算平衡的二叉排序树BT的平均查找长度，输出结果。 
答案
#include <stdio.h>#include <malloc.h>typedef struct BiTnode{int data;struct BiTnode *lchild,*rchild;}BiTnode,*BiTree;BiTree search_tree(BiTree T,int keyword,BiTree *father){BiTree p;*father = NULL;p = T;while (p && p->data!=keyword){*father = p;if (keyword < p->data)p = p->lchild;elsep = p->rchild;}return p;}BiTree creat_tree(int count){BiTree T,p;int i = 1;while (i <= count){if (i == 1){p = (BiTnode *)malloc(sizeof(BiTree));if (!p)return NULL;T = p;scanf("%d",&p->data);p->lchild = p->rchild = NULL;i++;}else{int temp;scanf("%d",&temp);search_tree(T,temp,&p);if (temp < p->data){p->lchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->lchild)return NULL;p = p->lchild;}else{p->rchild = (BiTnode *)malloc(sizeof(BiTnode));if (!p->rchild)return NULL;p = p->rchild;}p -> data = temp;p -> lchild = p->rchild = NULL;i++;}}return T;}int insert_tree(BiTree *T,int elem){BiTree s,p,father;s = (BiTnode *)malloc(sizeof(BiTnode));if (!s)return -1;s->data = elem;s->lchild = s->rchild = NULL;p = search_tree(*T,elem,&father);if (!p)return -1;if (father == NULL)*T = s;else if (elem < father->data)father->lchild = s;elsefather->rchild = s;return 0;}int delete_tree(BiTree *T,int elem){BiTree s,p,q,father;p = search_tree(*T,elem,&father);if(!p)return -1;if(!p->lchild){if (father == NULL){*T = p->rchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->rchild;elsefather->rchild = p->rchild;free(p);return 0;}elseif(!p->rchild){if (father == NULL){*T = p->lchild;free(p);return 0;}if (p == father->lchild)father->lchild = p->lchild;elsefather->rchild = p->lchild;free(p);return 0;}else{q = p;s = p->lchild;while (s->rchild){q = s;s = s->rchild;}p->data = s->data;if (q != p)q->rchild = s->lchild;elseq->lchild = s->lchild;free(s);return 0;}}main(){}这个2叉排序数存储的数据类型是int,要存储其他类型的数据,修改节点中的数据类型