erchashu.c

erchashu.c

#define MaxSize 20
#include<iostream>
#include<cstdlib>
using namespace std;

//1、定义二叉链表（P121）
typedef struct BiTNode{
char data;
struct BiTNode *lchild,*rchild; 
}BiTNode,*BiTree;


//2、先序遍历的顺序建立二叉链表（P126）
void CreatBiTree(BiTree &T)
{
char ch;
cin>>ch;
if(ch=='#') T=NULL;
else
{
T = new BiTNode;
T->data = ch;
CreatBiTree(T->lchild);
CreatBiTree(T->rchild);
}
}
//3、中序遍历二叉树(P123)
void InOrderTraverse(BiTree T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data;
InOrderTraverse(T->rchild);
}
}  

//4、先序遍历二叉树（模仿中序）
void PreOrderTraverse(BiTree T)
{
if(T)
{
cout<<T->data;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}




//5、后序遍历二叉树（模仿中序）
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data;
}
} 

//6、计算二叉树的深度（P127）
int  Depth(BiTree T)
{
int m,n;
if(T==NULL) return 0;
else
{
m=Depth(T->lchild);
n=Depth(T->rchild);
if(m>n) return(m+1);
else return(n+1);
}
}
//7、统计二叉树中结点的个数(P128)
int NodeCount(BiTree T)
{
if(T==NULL) return 0;
else return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
}

//8、按层遍历二叉树
void LevelOrder(BiTree T)
{
   BiTree p;
   BiTree qu[MaxSize];
   int front,rear;
   front=rear=0;
   qu[rear]=T;
   rear++;
   while(front!=rear)
   {
       p=qu[front];
front++;
       cout<<p->data;
       if(p->lchild!=NULL)
{
qu[rear]=p->lchild;
rear++;
}   
       if(p->rchild!=NULL)
{
qu[rear]=p->rchild;
rear++;
}    
   }    
}

//*****************主函数******************
//要求：创建实验讲义所示的二叉树，注意按照提示的顺序
//输入结点，之后对该二叉树前序、中序、后序、按层遍历，并计算其深度
//统计其结点个数。 
int main()
{
BiTree T;
   cout<<"请输入树中结点:"<<endl; 
   CreatBiTree(T);
   
   cout<<"先序遍历序列为:";
   PreOrderTraverse(T);
   cout<<endl;
   
   cout<<"中序遍历序列为:";
   InOrderTraverse(T);
cout<<endl; 

cout<<"后序遍历序列为:";
   PostOrderTraverse(T); 
   cout<<endl;

cout<<"按层遍历序列为:";
   LevelOrder(T); 
   cout<<endl;

cout<<"树的高度:";
cout<<Depth(T)<<endl; 

cout<<"统计节点总数为:"<<NodeCount(T)<<endl;

return 0;	  
}