数据结构实验报告-实现二叉树的基本操作-用顺序存储和链式存储结构

#include"base.h" // 公用头文件、公共常量及公共函数等 #include"bitree.h" // 二叉树二叉链表基本操作 void Menu(); // 菜单函数 void Produce(char *str); // 随机产生二叉树先序序列函数 int main() // 主函数 { BiTree T,bt,insert_bt; char cmd,str[MAXSIZE],elem; int loc,temp; InitBiTree(T); // 初始化二叉链表二叉树 Menu(); // 显示菜单 while(1) { ClearAera(); // 清空结果显示区 SetColor(3 ); printf("请选择操作：(按‘Q'退出)"); SetColor(); cmd = getch(); ClearAera(); fflush(stdin); switch(cmd) { case '0':// 随机创建一棵二叉树 while(cmd != 'y' && cmd != 'Y') { Produce(str); // 随机产生二叉树先序序列 CreateBiTree(T,str);// 用此序列建树 PrintBiTree(T); // 树形结构显示 printf(" 使用屏幕右下角创建的二叉树<Y/N>?\n"); ShowBiTree(T); // 广义表形式显示 cmd = getch(); ClearAera(); } break; case '1':// 手动创建一棵二叉树 printf(" 请按二叉树先序序列输入二叉树：(空结点用空格' '表示)\n "); CreateBiTree(T); PrintBiTree(T); // 树形结构显示二叉树 ClearAera(); printf(" 二叉树创建成功!\n"); ShowBiTree(T); // 广义表形式显示 getch(); break; case '2':// 销毁二叉树 DestroyBiTree(T); printf(" 二叉树已被销毁!"); PrintBiTree(T); getch(); break; case '3':// 清空二叉树 ClearBiTree(T); printf(" 二叉树已被清空!"); PrintBiTree(T); getch(); break; case '4':// 判空 if(BiTreeEmpty(T)) printf("二叉树是空二叉树。"); else printf("二叉树非空"); getch(); break; case '5':// 求深度 printf("深度是 %d",BiTreeDepth(T)); getch(); break; case '6':// 求左孩子 printf("你想求哪个字符的左孩子？"); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); // 查找指定的结点值elem if(!bt) printf(" 你输入的结点不存在!请重新输入："); }while(!bt); ClearAera(); bt = LeftChild(T,bt); // 求左孩子 if(bt) printf(" %c的左孩子是%c",elem,bt->data); else printf(" %c没有左孩子",elem); getch(); break; case '7':// 求右孩子 printf(" 你想求哪个字符的右孩子？"); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); if(!bt) printf(" 你输入的结点不存在!请重新输入："); }while(!bt); ClearAera(); bt = RightChild(T,bt); if(bt) printf(" %c的右孩子是%c",elem,bt->data); else printf(" %c没有右孩子",elem); getch(); break; case '8':// 求左兄弟 printf(" 你想求哪个字符的左兄弟？"); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); if(!bt) printf(" 你输入的结点不存在!请重新输入："); }while(!bt); ClearAera(); bt = LeftSibling(T,bt); if(bt) printf(" %c的左兄弟是%c",elem,bt->data); else printf(" %c没有左兄弟",elem); getch(); break; case '9':// 求右兄弟 printf(" 你想求哪个字符的右兄弟？"); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); if(!bt) printf("你输入的结点不存在!请重新输入："); }while(!bt); ClearAera(); bt = RightSibling(T,bt); if(bt) printf(" %c的右兄弟是%c。",elem,bt->data); else printf(" %c没有右兄弟。",elem); getch(); break; case 'a':// 先序遍历 if(!BiTreeEmpty(T)) { printf("先序遍历序列为："); PreOrderTraverse(T,Visit); } else printf("二叉树空，请先建树!"); getch(); break; case 'b':// 中序遍历 if(!BiTreeEmpty(T)) { printf("中序遍历序列为："); InOrderTraverse(T,Visit); } else printf("二叉树空，请先建树!"); getch(); break; case 'c':// 后序遍历 if(!BiTreeEmpty(T)) { printf("后序遍历序列为："); PostOrderTraverse(T,Visit); } else printf(" 二叉树空，请先建树!"); getch(); break; case 'd':// 层次遍历 if(!BiTreeEmpty(T)) { printf("层次遍历序列为："); LevelOrderTraverse(T,Visit); } else printf("二叉树空，请先建树!"); getch(); break; case 'e':// 插入一棵二叉树为另一棵二叉树的子树 do{ // 随机创建一棵右孩子为空 Produce(str); // 且层数小于4的树 CreateBiTree(insert_bt,str); }while(insert_bt->rchild||BiTreeDepth(insert_bt) > 3); PrintBiTree(insert_bt); // 新创建的树 printf(" 先随机创建一棵右子树空的二叉树如图\n"); getch(); PrintBiTree(T); printf(" 你想插入这棵树为原树哪个结点的子树 :"); bt = SearchBiTree(T,getchar()); ClearAera(); printf(" 你想插入为 0. 左孩子 1. 右孩子 :"); fflush(stdin); scanf("%d",&loc); ClearAera(); if(!InsertChild(T, bt, loc, insert_bt)) printf(" 插入出错!"); else{ printf(" 插入成功!插入后T广义表形式为:\n"); ShowBiTree(T); } PrintBiTree(T); // 显示插入后的树 getch(); break; case 'f':// 删除指定结点的子树 printf(" 你想删除哪个结点的子树?"); fflush(stdin); bt = SearchBiTree(T,getchar()); printf(" 你想删除 0.左子树 1.右子树: "); fflush(stdin); scanf("%d",&loc); ClearAera(); if(!DeleteChild(T,bt,loc)) printf(" 删除出错!"); else printf(" 删除成功，查看屏幕右下角二叉树状态。"); PrintBiTree(T); getch(); break; case 'g':// 返回根节点 if(!BiTreeEmpty(T)) printf(" 二叉树的根结点是 %c。",Root(T)->data); else printf(" 二叉树为空，不存在根节点!"); getch(); break; case 'h':// 返回先序序列第i个结点的值 printf("请输入一个结点的先序序列序号: "); scanf("%d",&loc); temp = loc; ClearAera(); elem = Value(T,temp); if(elem == ' ') printf(" 该结点不存在。"); else printf(" 先序序列第%d个结点值为%c",loc,elem); getch(); break; case 'i':// 求父节点 printf(" 你想求哪个字符的父节点？"); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); if(!bt) printf(" 你输入的结点不存在!请重新输入："); }while(!bt); ClearAera(); bt = Parent(T,bt); if(bt) printf(" %c 的父节点为 %c。",elem,bt->data); else printf(" %c 没有父节点。",elem); getch(); break; case 'j':// 结点赋值 printf(" 请输入要赋值的结点: "); do{ elem = getchar(); ClearAera(); bt = SearchBiTree(T,elem); if(!bt) printf(" 你输入的结点不存在!请重新输入："); }while(!bt);; ClearAera(); printf(" 请输入新值: "); fflush(stdin); elem = getchar(); Assign(T,bt,elem); printf(" 赋值成功，请查看屏幕右下角的二叉树状态."); PrintBiTree(T); getch(); break; case 'Q':// 退出 case 'q': exit(0); } } return 0; } void Menu() // 显示菜单函数 { printf(" ********************抽象类型二叉树基本操作**************"); printf("\n\n 0. 随机创建 CreateBiTree() a. 先序遍历 PreOrderTraverse()"); printf("\n\n 1. 手动创建 CreateBiTree() b. 中序遍历 InOrderTraverse()"); printf("\n\n 2. 销毁 DestroyBiTree() c. 后序遍历 PostOrderTraverse()"); printf("\n\n 3. 清空 ClearBiTree() d. 层次遍历 LevelOrderTraverse()"); printf("\n\n 4. 判空 BiTreeEmpty() e. 插入子树 InsertChild()"); printf("\n\n 5. 求深度 BiTreeDepth() f. 删除子树 DeleteChild()"); printf("\n\n 6. 求左孩子 LeftChild() g. 求根结点 Root()"); printf("\n\n 7. 求右孩子 RightChild() h. 求结点值 Value()"); printf("\n\n 8. 求左兄弟 LeftSibling() i. 求父节点 Parent"); printf("\n\n 9. 求右兄弟 RightSibling() j. 结点赋值 Assign"); printf("\n------------------------------------------------------------------\n"); } void Produce(char *str) // 用随机数产生二叉树层次字符序列 // 使所有节点的字符不相同，空节点用‘&’表示 { int exist[27] , i , elem, maxnodes = rand()%41; while( maxnodes < 15 || maxnodes > 31) maxnodes = rand()%41; /* 随机产生一个 大于15小于31的随机数作为结点个数 */ for(i = 0; i < 27 ;i++) exist[i] = 0; // 初始化存在数组，用于使所有结点值不同 i = 1; while(i < maxnodes) { elem = rand() % 26 ; if(!exist[elem] && str[i/2] != '&') // 结点未生成且存在父节点 { str[i++] = elem + 'A'; exist[elem] = 1; }