求二叉树结点路径.doc

《求二叉树结点路径.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、求二叉树上结点的路径要求在采用链式存储结构存储的二叉树上。以T指向根节点，p指向任一给定的结点，编程实现如下功能：（1）建立一棵二叉树存储结构；（2）求二叉树的前序遍历序列；（3）求二叉树的中序遍历序列；（4）求二叉树的后序遍历序列；（5）求给定的结点的路径。#include#include#include#include#defineNodeNum100typedefstructnode{chardata;str

2、uctnode*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

3、);}}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)//------二叉树的后序遍历

4、{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!=

5、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==

6、-1));//------通过后序遍历非递归算法循环语句实现查找}intmenuselect()//------主菜单显示{intsn;cout<

7、"0退出学生信息管理系统"<>sn;if(sn<0

8、

9、sn>5)cout<<"输入错误，请重新输入"<

10、<>item;AllPath(T,item);b