求二叉树结点路径.doc

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

#include<iostream.h>
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define NodeNum 100
typedef struct node
{
char 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;
else
{
T=(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 STACK1[NodeNum],p=T;
char STACK2[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;
}
else
p=NULL;
}
}while(!(p==NULL&&top==-1)); //------通过后序遍历非递归算法循环语句实现查找
}
int menuselect() //------主菜单显示
{
int sn;
cout<<endl;
cout<<"===========二叉树结点路径============="<<endl;
cout<<" 1 建立二叉树 "<<endl;
cout<<" 2 前序遍历输出二叉树 "<<endl;
cout<<" 3 中序遍历输出二叉树 "<<endl;
cout<<" 4 后序遍历输出二叉树 "<<endl;
cout<<" 5 求给定结点路径 "<<endl;
cout<<" 0 退出学生信息管理系统 "<<endl;
cout<<"=========================================";
cout<<endl;
for( ; ; )
{
cin>>sn;
if(sn<0||sn>5)
cout<<"输入错误，请重新输入"<<endl;
else
break;
}
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;
{
cout<<"请输入要查找的结点：";
cin>>item;
AllPath(T,item);
break;
}
case 0:cout<<" 退出学生信息管理系统 "<<endl;
flag=0;
break;
}

}
return 0;
}