二叉树

290112011

#include<stdio.h>
#include<string.h>
#include<iostream>
#include<malloc.h>
#include<math.h>
using namespace std;
#define MAXSIZE 100
#define OK 1
typedef int Ststus ;
typedef  char  TElemType  ;
typedef struct BiThrNode
{
TElemType data;
struct BiThrNode *lchild,*rchild;
}BiThrNode,*BiTree;
//先序建立
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);
T=new BiThrNode;
if(ch=='#') T=NULL;
else
{
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return ;
}
//先序遍历
void PreOrder(BiTree T)
{
if(T)
{
cout<<T->data<<" ";
PreOrder(T->lchild);
PreOrder(T->rchild);
}
else return;
}
//中序遍历
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild);
cout<<T->data<<" ";
InOrder(T->rchild);
}
else return ;
}
//后序遍历
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild);
PostOrder(T->rchild);
cout<<T->data<<" ";
}
else
return ;
}
void ClearBiTree(BiTree *T)
{
if(*T)
{
if((*T)->lchild)ClearBiTree(&(*T)->lchild);
if((*T)->rchild)ClearBiTree(&(*T)->rchild);
free(T);//%%
(*T)=NULL;
}
}
//判断树是否为空
int IsEmpty(BiTree T)
{
if(T)return 0;
else return 1;
}
//计算树的深度
int GetDepth(BiTree T)
{
int l=0,r=0;
if(T->lchild)
l=GetDepth(T->lchild);
else l=0;
if(T->rchild)
r=GetDepth(T->rchild);
else r=0;
return max(r,l)+1;
}
//查询根节点
TElemType GetRoot(BiTree T)
{
if(IsEmpty(T))
return NULL;
else
return T->data;
}
//交换左右子树
void Exchange(BiTree T)
{
BiTree temp = NULL;
if(T->lchild == NULL && T->rchild == NULL)
return;
else
{
temp = T->lchild;
T->lchild = T->rchild;
T->rchild = temp;
}
if(T->lchild)
Exchange(T->lchild);
if(T->rchild)
Exchange(T->rchild);
}
int main()
{
BiTree  T;
CreateBiTree(T);
cout<<"先序遍历"<<endl;
PreOrder(T);
cout<<"中序遍历"<<endl;
InOrder(T);
cout<<"后序遍历"<<endl;
PostOrder(T);
cout<<"树的深度:"<<GetDepth(T)<<endl;
cout<<"树的根节点:"<<GetRoot(T)<<endl;
if(IsEmpty(T))
cout<<"空"<<endl;
else cout<<"非空"<<endl;
Exchange(T);
PreOrder(T);ClearBiTree(&T);
if(IsEmpty(T))
cout<<"空"<<endl;
else cout<<"非空"<<endl;
}