数据结构C语言课设-二叉树排序.docx

题目:二叉排序树的实现1 内容和要求1） 编程实现二叉排序树， 包括生成、插入，删除；2） 对二叉排序树进行先根、中根、 和后根非递归遍历；3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。4） 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。前中后根遍历需要用到栈的数据结构，分模块编写栈与遍历代码。要求对比二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock（）函数记录查找时间来对比查找效率。 2.2关键代码2.2.1树的基本结构定义及基本函数typedef structKeyType key; ElemType;typedef struct BiTNode /定义链表ElemType data;struct BiTNode *lchild, *rchild;BiTNode, *BiTree, *SElemType;/销毁树int DestroyBiTree(BiTree &T)if (T != NULL)free(T);return 0;/清空树int ClearBiTree(BiTree &T) if (T != NULL)T-lchild = NULL;T-rchild = NULL;T = NULL;return 0;/查找关键字,指针p返回int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p)if (!T)p = f;return FALSE;else if EQ(key, T-data.key)p = T;return TRUE;else if LT(key, T-data.key)return SearchBST(T-lchild, key, T, p);elsereturn SearchBST(T-rchild, key, T, p);2.2.2二叉树的生成、插入，删除生成void CreateBST(BiTree &BT, BiTree p)int i;ElemType k;printf(请输入元素值以创建排序二叉树:n);scanf_s(%d, &k.key);for (i = 0; k.key != NULL; i+)/判断是否重复if (!SearchBST(BT, k.key, NULL, p)InsertBST(BT, k);scanf_s(%d, &k.key);elseprintf(输入数据重复！n);return;插入int InsertBST(BiTree &T, ElemType e) BiTree s, p;if (!SearchBST(T, e.key, NULL, p)s = (BiTree)malloc(sizeof(BiTNode);s-data = e;s-lchild = s-rchild = NULL;if (!p)T = s;else if LT(e.key, p-data.key)p-lchild = s;elsep-rchild = s;return TRUE;else return FALSE;删除/某个节点元素的删除int DeleteEle(BiTree &p)BiTree q, s;if (!p-rchild) /右子树为空q = p;p = p-lchild;free(q);else if (!p-lchild) /左子树为空q = p;p = p-rchild;free(q);elseq = 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;delete s;return TRUE;/整棵树的删除int DeleteBST(BiTree &T, KeyType key) /实现二叉排序树的删除操作if (!T)return FALSE;elseif (EQ(key, T-data.key) /是否相等return DeleteEle(T);else if (LT(key, T-data.key) /是否小于return DeleteBST(T-lchild, key);elsereturn DeleteBST(T-rchild, key);return 0;2.2.3二叉树的前中后根遍历栈的定义typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;int InitStack(SqStack &S) /构造空栈S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType);if (!S.base) exit(OVERFLOW);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/InitStackint Push(SqStack &S, SElemType e) /插入元素e为新栈顶if (S.top - S.base = S.stacksize)S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType);if (!S.base) exit(OVERFLOW);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;/Pushint Pop(SqStack &S, SElemType &e) /删除栈顶,应用e返回其值if (S.top = S.base) return ERROR;e = *-S.top;return OK;/Popint StackEmpty(SqStack S) /判断是否为空栈if (S.base = S.top) return TRUE;return FALSE;先根遍历int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e) SqStack S;BiTree p;InitStack(S);p = T;while (p | !StackEmpty(S)if (p)Push(S, p);if (!Visit(p-data) return ERROR;p = p-lchild;elsePop(S, p);p = p-rchild;return OK;中根遍历int InOrderTraverse(BiTree T, int(*Visit)(ElemType e) SqStack S;BiTree p;InitStack(S);p = T;while (p | !StackEmpty(S)if (p)Push(S, p);p = p-lchild;elsePop(S, p);if (!Visit(p-data) return ERROR;p = p-rchild;return OK;后根遍历int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e) SqStack S, SS;BiTree p;InitStack(S);InitStack(SS);p = T;while (p | !StackEmpty(S)if (p)Push(S, p);Push(SS, p);p = p-rchild;elseif (!StackEmpty(S)Pop(S, p);p = p-lchild;while (!StackEmpty(SS)Pop(SS, p);if (!Visit(p-data) return ERROR;return OK;2.2.4利用数组存储一个班学生信息ElemType a = 51, 陈继真, 88,82, 黄景元, 89,53, 贾成, 88,44, 呼颜, 90,25, 鲁修德, 88,56, 须成, 88,47, 孙祥, 87,38, 柏有患, 89,9, 革高, 89,10, 考鬲, 87,31, 李燧, 86,12, 夏祥, 89,53, 余惠, 84,4, 鲁芝, 90,75, 黄丙庆, 88,16, 李应, 89,87, 杨志, 86,18, 李逵, 89,9, 阮小五, 85,20, 史进, 88,21, 秦明, 88,82, 杨雄, 89,23, 刘唐, 85,64, 武松, 88,25, 李俊, 88,86, 卢俊义, 88,27, 华荣, 87,28, 杨胜, 88,29, 林冲, 89,70, 李跃, 85,31, 蓝虎, 90,32, 宋禄, 84,73, 鲁智深, 89,34, 关斌, 90,55, 龚成, 87,36, 黄乌, 87,57, 孔道灵, 87,38, 张焕, 84,59, 李信, 88,30, 徐山, 83,41, 秦祥, 85,42, 葛公, 85,23, 武衍公, 87,94, 范斌, 83,45, 黄乌, 60,67, 叶景昌, 99,7, 焦龙, 89,78, 星姚烨, 85,49, 孙吉, 90,60, 陈梦庚, 95,;2.2.5数组查询函数void ArraySearch(ElemType a, int key, int length)int i;for (i = 0; i = length; i+)if (key = ai.key)cout 学号： ai.key 姓名： 成绩： ai.grade key;if (!key)break;/通过二叉树搜索记录start = clock();SearchBST(BT, key, NULL, p);cout 学号： data.key 姓名： 成绩： data.grade endl;finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;cout 二叉树查询时间： duration endl;/通过数组搜索记录start = clock();ArraySearch(a, key, length);finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;cout 数组查询时间： duration endl;3.2.2测试结果截图3.2.3结论：经过三次查询可以看出，二叉树的查找效率要高于数组。当二叉排序树为满二叉树时，树的查找效率最高，因为二叉排序树的平均查找长度和logn是等数量级的，树的深度越小，查找效率越高。因此，要提高二叉排序树的查找