求二叉树结点路径.doc

求二叉树上结点的路径要求在采用链式存储结构存储的二叉树上。以T指向根节点，p指向任一给定的结点，编程实现如下功能：（1） 建立一棵二叉树存储结构；（2） 求二叉树的前序遍历序列；（3） 求二叉树的中序遍历序列；（4） 求二叉树的后序遍历序列；（5） 求给定的结点的路径。#include#include#include#include#define NodeNum 100typedef struct nodechar data;struct node *lchild,*rchild;BTNode,*BTREE;void VISIT(char e) /-输出语句printf(%c,e);void BUILDBT(BTREE &T) /-利用前序遍历构建二叉树char ch;scanf(%c,&ch);if(ch= )T=NULL;elseT=(BTREE)malloc(sizeof(BTNode);T-data=ch;BUILDBT(T-lchild);BUILDBT(T-rchild);void PREORDER(BTREE T) /-二叉树的前序遍历if(T!=NULL)VISIT(T-data);PREORDER(T-lchild);PREORDER(T-rchild);void INORDER(BTREE T) /-二叉树的中序遍历if(T!=NULL)INORDER(T-lchild);VISIT(T-data);INORDER(T-rchild);void POSTORDER(BTREE T) /-二叉树的后序遍历if(T!=NULL)POSTORDER(T-lchild);POSTORDER(T-rchild);VISIT(T-data);void AllPath(BTREE T,char item) /-求得定路径结点 BTREE STACK1NodeNum,p=T; char STACK2NodeNum,top=-1,flag;/-定义一个堆栈，保存所找到的结点if(T!=NULL&T-data!=item) /-假如所找的结点不是根结点dowhile(p!=NULL)STACK1+top=p;STACK2top=0;p=p-lchild;p=STACK1top;flag=STACK2top-;if(flag=0)STACK1+top=p;STACK2top=1;p=p-rchild;elseif(p-data=item)while(top!=-1)printf(%4c,STACK1top-data);break; else p=NULL;while(!(p=NULL&top=-1); /-通过后序遍历非递归算法循环语句实现查找 int menuselect() /-主菜单显示int sn;coutendl;cout=二叉树结点路径=endl;cout 1 建立二叉树 endl;cout 2 前序遍历输出二叉树 endl;cout 3 中序遍历输出二叉树 endl;cout 4 后序遍历输出二叉树 endl;cout 5 求给定结点路径 endl;cout 0 退出学生信息管理系统 endl;cout=;coutsn;if(sn5)cout输入错误，请重新输入endl;elsebreak;return sn;int main()BTNode *T;char item;int flag=1;while(flag)switch(menuselect()case 1:cout 建立一个二叉树： endl; BUILDBT(T); break;case 2:cout 前序遍历输出二叉树为： endl; PREORDER(T); break;case 3:cout 中序遍历输出二叉树为： endl; INORDER(T); break;case 4:cout 后序遍历输出二叉树为： endl; POSTORDER(T); break; case 5:cout 求给定结点路径： endl; coutitem; AllPath(T,item); break; case 0:cout 退出学生信息管理系统 endl; flag=0; break;return 0;