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

题目:二叉排序树的实现1 内容和要求1） 编程实现二叉排序树， 包括生成、插入，删除；2） 对二叉排序树进行先根、中根、 和后根非递归遍历；3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来4） 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?2 解决方案和关键代码2.1 解决方案：先实现二叉排序树的生成、插入、删除，编写 DisplayBST 函数把遍历结果用树的形状表示出来前中后根遍历需要用到栈的数据结构，分模块编写栈与遍历代码要求对比二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用 clock（）函数记录查找时间来对比查找效率 2.2 关键代码2.2.1 树的基本结构定义及基本函数typedef struct{KeyType 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);}else{printf("输入数据重复！\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);}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;delete s;}return TRUE;}//整棵树的删除int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作{if (!T){return FALSE;}else{if (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;}else{Pop(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;}else{Pop(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;}else{if (!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 > key;if (!key)break;//通过二叉树搜索记录start = clock();SearchBST(BT, key, NULL, p);cout data.key data.name 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 结论：经过三次查询可以看出，二叉树的查找效率要高于数组。

当二叉排序树为满二叉树时，树的查找效率最高，因为二叉排序树的平均查找。