shu3.cpp

数据结构二叉树的先序

#include<iostream.h> 
#include<stdlib.h> 
#include<stdio.h>
#define MAX_TREE_SIZE 100 
#define STACK_INIT_SIZE 100 

//定义树的结构和栈的结构 

typedef struct BiTNode 
{ 
char data; 
struct BiTNode *lchild ,*rchild; 
}BiTNode,*BiTree; 


typedef struct Stack 
{ 
BiTree *top; 
BiTree *base; 
int stacksize; 
}Sqstack; 



//构造空栈的函数 

bool InitStack(Sqstack &S) 
{ 
S.base=((BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTNode))); 
if(!S.base) 
cout<<0; 
S.top=S.base; 
S.stacksize=STACK_INIT_SIZE ; 
return 1; 
} 

//下列四个函数分别是取栈顶元素，元素进栈，元素出栈和判断栈空的函数 
bool GetTop(Sqstack &S,BiTree &e) 
{ 
if(S.top==S.base) 
return 0; 
e=*(S.top-1); 
return 1; 
} 

bool Push(Sqstack &S,BiTree &e) 
{ 
*S.top++=e; 
return 1; 
} 

bool Pop(Sqstack &S,BiTree &e) 
{ 
if(S.top==S.base) 
return 0; 
e=*--S.top; 
return 1; 
} 

bool StackEmpty(Sqstack &S) 
{ 
if(S.top==S.base) 
{ 
return 1; 
} 
return 0; 
} 

//建立二叉数用的函数 
bool CreateBiTree(BiTree &T) 
{ 

char b; 
cin>>b; 
if(b=='#') 
T=NULL; 
else 
{ 
if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) 
cout<<0; 
T->data=b; 
CreateBiTree(T->lchild); 
CreateBiTree(T->rchild); 
} 
return 1; 
} 

void DisplayBinTree(BiTree &T)
{
BiTree stack[MAX_TREE_SIZE],p;
int level[MAX_TREE_SIZE],top,n,i;
if(T!=NULL)
{
   top=1;
   stack[top]=T;
   level[top]=3;
   while(top>0)
   {
    p=stack[top];
    n=level[top];
    for(i=1;i<=n;i++)
    printf(" ");
    printf("%c\n",p->data);
    top--;
    if(p->lchild!=NULL)
    {
     top++;
     stack[top]=p->lchild;
     level[top]=n+3;
    }
    if(p->rchild!=NULL)
    {
     top++;
     stack[top]=p->rchild;
     level[top]=n+3;
    }
   }
}
}

//下面三个函数分别是前序，中序和后序遍历二叉树用的函数 
void PreOrderTraverse(BiTree &T) 
{ 
if(T==NULL) 
return ; 
cout<<T->data; 
cout<<" "; 
PreOrderTraverse(T->lchild); 
PreOrderTraverse(T->rchild); 
} 


void InOrderTraverse(BiTree T) 
{
if(T==NULL) 
return ; 	
InOrderTraverse(T->lchild);
cout<<T->data; 
cout<<" "; 
InOrderTraverse(T->rchild);
} 

void PostOrderTraverse(BiTree &T) 
{ 
if(T==NULL) 
return ; 
PostOrderTraverse(T->lchild); 
PostOrderTraverse(T->rchild); 
cout<<T->data; 
cout<<" "; 
} 

//主函数 
void main() 
{ 
BiTree T; 
u: 
cout<<"\n\n本系统可以提供下列操作："<<endl; 
cout<<"1.建立一棵二叉树"<<endl; 
cout<<"2.先序遍历此二叉树"<<endl; 
cout<<"3.中序遍历此二叉树"<<endl; 
cout<<"4.后序遍历此二叉树"<<endl; 
cout<<"5.用凹入表横向打印二叉树"<<endl;
cout<<"0.结束程序\n"<<endl; 
int a; 
cin>>a; 
switch(a) 
{ 
case 1: 
cout<<"请输入数据建立一棵二叉树"<<endl; 
CreateBiTree(T); 
goto u; 
case 2: 
PreOrderTraverse(T); 
goto u; 
case 3: 
InOrderTraverse(T); 
goto u; 
case 4:
PostOrderTraverse(T); 
goto u; 
case 5:	
DisplayBinTree(T);
goto u; 
case 0: 
goto end; 
default : 
cout<<"您必须先进行1操作才能进行其它操作 "<<endl; 
goto u; 
} 
end: 
cout<<endl; 
}