求二叉树结点路径

求二叉树上结点的路径要求在采用链式存储结构存储的二叉树上。以T指向根节点，p指向任一给定的结点，编程实现如下功能：（1）建立一棵二叉树存储结构；（2）求二叉树的前序遍历序列；（3）求二叉树的中序遍历序列；（4）求二叉树的后序遍历序列；（5）求给定的结点的路径。#includeiostream.h#includestdio.h#includestring.h#includestdlib.h#defineNodeNum100typedefstructnode{chardata;structnode*lchild,*rchild;}BTNode,*BTREE;voidVISIT(chare)//---------输出语句{printf(%c,e);}voidBUILDBT(BTREE&T)//------利用前序遍历构建二叉树{charch;scanf(%c,&ch);if(ch=='')T=NULL;else{T=(BTREE)malloc(sizeof(BTNode));T-data=ch;BUILDBT(T-lchild);BUILDBT(T-rchild);}}voidPREORDER(BTREET)//------二叉树的前序遍历{if(T!=NULL){VISIT(T-data);PREORDER(T-lchild);PREORDER(T-rchild);}}voidINORDER(BTREET)//------二叉树的中序遍历{if(T!=NULL){INORDER(T-lchild);VISIT(T-data);INORDER(T-rchild);}}voidPOSTORDER(BTREET)//------二叉树的后序遍历{if(T!=NULL){POSTORDER(T-lchild);POSTORDER(T-rchild);VISIT(T-data);}}voidAllPath(BTREET,charitem)//-----求得定路径结点{BTREESTACK1[NodeNum],p=T;charSTACK2[NodeNum],top=-1,flag;//----定义一个堆栈，保存所找到的结点if(T!=NULL&&T-data!=item)//-----假如所找的结点不是根结点do{while(p!=NULL){STACK1[++top]=p;STACK2[top]=0;p=p-lchild;}p=STACK1[top];flag=STACK2[top--];if(flag==0){STACK1[++top]=p;STACK2[top]=1;p=p-rchild;}else{if(p-data==item){while(top!=-1)printf(%4c,STACK1[top--]-data);break;}elsep=NULL;}}while(!(p==NULL&&top==-1));//------通过后序遍历非递归算法循环语句实现查找}intmenuselect()//------主菜单显示{intsn;coutendl;cout===========二叉树结点路径=============endl;cout1建立二叉树endl;cout2前序遍历输出二叉树endl;cout3中序遍历输出二叉树endl;cout4后序遍历输出二叉树endl;cout5求给定结点路径endl;cout0退出学生信息管理系统endl;cout=========================================;coutendl;for(;;){cinsn;if(sn0||sn5)cout输入错误，请重新输入endl;elsebreak;}returnsn;}intmain(){BTNode*T;charitem;intflag=1;while(flag){switch(menuselect()){case1:cout建立一个二叉树：endl;BUILDBT(T);break;case2:cout前序遍历输出二叉树为：endl;PREORDER(T);break;case3:cout中序遍历输出二叉树为：endl;INORDER(T);break;case4:cout后序遍历输出二叉树为：endl;POSTORDER(T);break;case5:cout求给定结点路径：endl;{cout请输入要查找的结点：;cinitem;AllPath(T,item);break;}case0:cout退出学生信息管理系统endl;flag=0;break;}}return0;}