#include<stdio.h>
#define N 10
using namespace std
char *a
typedef struct NODE{
char data
struct NODE *lch, *rch,*parent
} *BINTREE,Node
void visit(char data){
printf("%5c",data)
}
void preorder(BINTREE T){ // 先根序周游
BINTREE stack[50]
BINTREE p
p=T
int s=0
if(p==NULL)return
while(1)
{ visit(p->data)
while(p->lch!=NULL) {
stack[++s]=p
p=p->lch
visit(p->data) }
// cout<<" "<<s
while(1)
{ if((p=p->rch)!=NULL)
break
if(s==0)
return
p=stack[s--]
}
}
}
void inorder(BINTREE T)//中根序周游
{
Node *stack[100]
int top=0
stack[0]=T
while(top>0 ||stack[top]!=NULL)
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch
}
if(top>0)
{
printf("%5c",stack[--top]->data )
stack[top]=stack[top]->rch
}
}
}
void posorder1(BINTREE T)//后根序周游
{
Node *stack[100]
int top=0
int tag[100]
tag[0]=0
stack[0]=T
do
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch
tag[top]=0
}
while(tag[top-1]==1)
printf("%5c",stack[--top]->data )
if(top>0)
{
stack[top]=stack[top-1]->rch
tag[top-1]=1
tag[top]=0
}
} while(top!=0)
}
BINTREE Create(){//先根序树的建立
BINTREE T
char ch
cin>>ch
cout<<" ch="<<ch<<endl
if(ch=='#')
T=NULL
else{
if(!(T=(BINTREE )malloc(sizeof(Node))))
printf("Error!")
T->data=ch
T->lch=Create()
T->rch=Create()
}
return T
}
void main(){
freopen("D:\\input.txt","r",stdin)
BINTREE T
T=Create()
cout<<"先根序遍历 "
preorder(T)
cout<<endl
cout<<"中根序遍历 "
inorder(T)
cout<<endl
cout<<"后根序遍历 "
posorder1(T)
cout<<endl
cout<<endl
}
在D盘建立一个input.txt的文件,输入数的内容,输入顺序为先序根遍历的顺序,叶子节点的left和right用#代替即可。
void PreOrderTraverse(BiTree T) /*先序遍历*/{
if(T!=NULL)
{
printf("%c ",T->data)
PreOrderTraverse(T->lchild)
PreOrderTraverse(T->rchild)
}
}
void InOrderTraverse(BiTree T)/*中序遍历*/
{
if(T!=NULL)
{
InOrderTraverse(T->lchild)
printf("%c ",T->data)
InOrderTraverse(T->rchild)
}
}
void PostOrderTraverse(BiTree T) /*后序遍历*/
{
if(T!=NULL)
{
PostOrderTraverse(T->lchild)
PostOrderTraverse(T->rchild)
printf("%c ",T->data)
}
}