#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;
}
- 1
- 2
- 3
- 4
- 5
前往页