数据结构实验 二叉树遍历与路径查找

#include<iostream> #include<stdio.h> #include<math.h> #include<malloc.h> using namespace std; #define MAXSIZE 100 int k=0; char nodes[100]; //二叉树的二叉链表存储表示 typedef struct BiNode{ char data; //结点数据域 struct BiNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; //创建队列 typedef struct{ struct BiNode* base[100]; int front,rear; }SqQueue; //函数 void CreateBiTree(BiTree &T);//按先序次序输入二叉树中结点的值创建二叉链表表示的二叉树T int nulltree(BiTree &T);//判断是否为空树 void PreOrderTraverse(BiTree T);//先序遍历 void InOrderTraverse(BiTree T);//中序遍历 void PostOrderTraverse(BiTree T);//后序遍历 void LevelOrderTraverse(BiTree T);//层次遍历 void FindPath(BiTree root,char ch);//求给定结点的路径 void Ask();//询问是否结束 //主函数 int main(){ int x,y,ant=1; BiTree tree[250]; char node;//储存要查找路径的节点 int Num;//定义功能序号 while(1)//循环主菜单，只可通过退出功能退出程序 { printf("***************************************\n"); printf("* 1.建立二叉树存储结构； *\n"); printf("* 2.修改已有的二叉树； *\n"); printf("* 3.求二叉树的先序遍历; *\n"); printf("* 4.求二叉树的中序遍历; *\n"); printf("* 5.求二叉树的后序遍历; *\n"); printf("* 6.求二叉树的层次结构; *\n"); printf("* 7.求根到给定结点的路径; *\n"); printf("* 0.退出. *\n"); printf("***************************************\n"); printf("\n"); printf("请选择你要操作的选项:"); A:if(scanf("%d",&Num)!=1){//识别功能序号 printf("输入错误，请重新输入！\n"); while(getchar()!='\n'); goto A;} switch(Num)//根据功能序号进行功能执行 { case 0: printf("是否确定退出？1.退出，其他.返回主菜单。\n"); if(scanf("%d",&x)!=1 || x!=1) { while(getchar()!='\n'); printf("未输入1，返回主菜单。\n"); break; } else { printf("程序结束！\n"); exit(0);//break while } case 1: printf("请按先序输入建立二叉树的序列(输入'#'表示为空):\n"); CreateBiTree(tree[ant]); printf("创建成功,保存至第%d个树\n",ant); ant++; Ask();break; case 2: printf("请选择你要修改的树(0<x<=%d，输入'0'取消):",ant-1); T:if(scanf("%d",&y)!=1||y<0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto T; } if(y==0) break; CreateBiTree(tree[y]); printf("修改成功!\n"); Ask();break; case 3: printf("请选择你要遍历的树(0<x<=%d):",ant-1); D:if(scanf("%d",&y)!=1||y<=0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto D; } if(nulltree(tree[y])!=1){ printf("第%d个树的先序遍历为:\n",y); PreOrderTraverse(tree[y]); printf("\n\n"); } Ask();break; case 4: printf("请选择你要遍历的树(0<x<=%d):",ant-1); E:if(scanf("%d",&y)!=1||y<=0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto E; } if(nulltree(tree[y])!=1){ printf("第%d个树的中序遍历为:\n",y); InOrderTraverse(tree[y]); printf("\n\n"); } Ask();break; case 5: printf("请选择你要遍历的树(0<x<=%d):",ant-1); F:if(scanf("%d",&y)!=1||y<=0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto F; } if(nulltree(tree[y])!=1){ printf("第%d个树的后序遍历为:\n",y); PostOrderTraverse(tree[y]); printf("\n\n"); } Ask();break; case 6: printf("请选择你要遍历的树(0<x<=%d):",ant-1); G:if(scanf("%d",&y)!=1||y<=0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto G; } if(nulltree(tree[y])!=1){ printf("第%d个树的层次遍历为：\n",y); LevelOrderTraverse(tree[y]); printf("\n\n"); } Ask();break; case 7: printf("请选择你要查看的树(0<x<=%d):",ant-1); H:if(scanf("%d",&y)!=1||y<=0 || y>ant-1) { printf("输入越界，请重试！"); while(getchar()!='\n'); goto H; } if(nulltree(tree[y])!=1){ printf("请输入结点名称:\n"); cin >> node; FindPath(tree[y],node); } Ask();break; default: break; } if((Num<0)||(Num>7))//如果输入功能执行号之外的数字则继续程序 printf("功能输入越界，程序继续。\n"); } system("pause"); return 0; } //判断是否为空树 int nulltree(BiTree &T){ if(T==NULL){ printf("该树为空！\n"); return 1; } return 0; } //按先序次序输入二叉树中结点的值创建二叉链表表示的二叉树T void CreateBiTree(BiTree &T){ char ch; cin>>ch; if(ch=='#') T=NULL; //递归结束，建空树 else { T=(BiTree)malloc(sizeof(BiNode)); T->data=ch;//生成根结点 nodes[k++]=ch; CreateBiTree(T->lchild); //递归创建左子树 CreateBiTree(T->rchild); //递归创建右子树 } } //先序遍历 void PreOrderTraverse(BiTree T){ if(T) { printf("%c ",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } //中序遍历 void InOrderTraverse(BiTree T){ //中序遍历二叉树T的递归算法 if(T){ InOrderTraverse(T->lchild); printf("%c ",T->data); InOrderTraverse(T->rchild); } } //后序遍历 void PostOrderTraverse(BiTree T){ if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c ",T->data); } } //层次遍历 void LevelOrderTraverse(BiTree T){ BiTree p; SqQueue Q; Q.rear=Q.front=0; if (T) { Q.base[Q.rear]=T; Q.rear=(Q.rear+1)%MAXSIZE; while (Q.front !=Q.rear) { p=Q.base[Q.front]; printf("%c ",p->data); Q.front=(Q.front+1)%MAXSIZE; if (p->lchild) { Q.base[Q.rear]=p->lchild; Q.rear=(Q.rear+1)%MAXSIZE; } if (p->rchild) { Q.base[Q.rear]=p->rchild; Q.rear=(Q.rear+1)%MAXSIZE; } } } } //求给定结点的路径 void FindPath(BiTree root,char ch){ typedef struct{ BiTree t; int tag;//tag=0表示访问左子树，tag=1表示访问右子树 }stack; stack s[100]; int top=0,flag=0,i,j=0; for(i=0;i<=k;i++) if(nodes[i]==ch) j++; if(j>1) { printf("此结点不唯一！\n"); return; } while(root||top) { while(root&&root->data!=ch) { s[++top].t=root; s[top].tag=0; root=root->lchild;//访问左子树 } if(root&&root->data==ch) { printf("从根节点到达结点%c的路径为：",ch); for(int i=1;i<=top;i++) printf("%c -> ",s[i].t->data); flag=1; printf("%c\n",ch); return ; } while(top&&s[top].tag==1) top--;//退栈 if(top) { s[top].tag=1; root=s[top].t->rchild;//访问右子树 } } if(flag==0) printf("不存在此结点！\n\n"); return; } //询问是否结束 void Ask() { int c; printf("\n您所需要的功能已实现，是否继续进行?\n\"1\" 继续; \"2\" 退出系统\n");//对程序接下来的使用进行查询 scanf("%d",&c); if (c==2){ printf("输入1确定退出:"); if(scanf("%d",&c)!=1 || c!=1) { while(getchar()!='\n'); printf("未输入\"1\"，程序继续。\n\n"); } else exit(0);//调用exit（0）来结束程序 } else if(c!=1){ while(getchar()!='\n'); printf("未输入\"2\"，程序继续。\n\n"); } }