二差树的简单应用
#include<iostream.h>typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T)
{
char ch;
cin>>ch;
if(ch=='0')
(*T)=NULL;
else
{
(*T)=new BiTNode;
(*T)->data =ch;
CreateBiTree(&(*T)->lchild );
CreateBiTree(&(*T)->rchild );
}
}
void InOrderOut(BiTree T)
{//中序遍历二叉树T
if(T)
{
InOrderOut(T->lchild );
cout<<T->data <<" ";
InOrderOut(T->rchild );
}
}
void PreOrderOut(BiTree T)
{//先序遍历二叉树T
if(T)
{
cout<<T->data <<" ";
PreOrderOut(T->lchild );
PreOrderOut(T->rchild );
}
}
void PostOrderOut(BiTree T)
{//后序遍历二叉树T
if(T)
{
PostOrderOut(T->lchild );
PostOrderOut(T->rchild );
cout<<T->data <<" ";
}
}
void LevelOrderOut(BiTree T)
{//层次遍历二叉树T
BiTree Queue[100];
int front ,rear;
if(T == NULL)
return ;//空二叉树，返回
front=-1;
rear=0;
Queue[rear]=T;//根结点入队
while (front!=rear)
{
front++;
cout<<Queue[front]->data<<" ";//访问队首结点的数值域
if(Queue[front]->lchild!=NULL)//将队首结点的左孩子节点入队列
{
rear++;
Queue[rear]=Queue[front]->lchild;
}
if(Queue[front]->rchild!=NULL)//将队首结点的右孩子节点入队列
{
rear++;
Queue[rear]=Queue[front]->rchild;
}
}
}
BiTree Swap(BiTree bt)
{
BiTree t,t1,t2;
if(bt==NULL)
t=NULL;
else
{
t=new BiTNode;
t->data=bt->data;
t1=Swap(bt->lchild);
t2=Swap(bt->rchild);
t->lchild=t2;
t->rchild=t1;
}
return t;
}
void main()
{
BiTree bt,t;
cout<<"\t\t 请按中序输入要建立的二叉树，为空时输入0： "<<endl;
CreateBiTree(&bt);
cout<<"先序遍历如下："<<endl;
PreOrderOut(bt);
cout<<endl;
cout<<"中序遍历如下："<<endl;
InOrderOut(bt);
cout<<endl;
cout<<"后序遍历如下："<<endl;
PostOrderOut(bt);
cout<<endl;
cout<<"按层遍历如下："<<endl;
LevelOrderOut(bt);
cout<<endl;
t=Swap(bt);
cout<<"交换后先序遍历如下："<<endl;
PreOrderOut(t);
cout<<endl;
cout<<"交换后中序遍历如下："<<endl;
InOrderOut(t);
cout<<endl;
cout<<"交换后后序遍历如下："<<endl;
PostOrderOut(t);
cout<<endl;
cout<<"交换后按层遍历如下："<<endl;
LevelOrderOut(t);
cout<<endl;
}
