#include <iostream>
#include <cstdio>
#include <malloc.h>
using namespace std;
#define FLASE 0
#define TRUE 1
typedef int TElemType;
typedef int Status;
typedef struct BiTNode
{
TElemType data; //结点的值
BiTNode *lchild, *rchild;//左右孩子指针
}BiTNode,*BiTree;
void InitBiTree(BiTree &T);
void DestroyBiTree(BiTree &T);
void PreOrderTraverse(BiTree T); //先序递归遍历T
void InOrderTraverse(BiTree T); //中序递归遍历T
void PostOrderTraverse(BiTree T); //后序递归遍历T
Status BiTreeEmpty(BiTree T); //判断是否为空
int BiTreeDepth(BiTree T); //T的深度
TElemType Root(BiTree T); //返回T的根
TElemType Value(BiTree p); //二叉树T存在，p指向T中的某个结点，结果返回p所指的结点
void CreateBiTree(BiTree &T); //按照先序次序输入二叉树中结点的值
void ExChangeTree(BiTree &T); //交换左右子树
int LeafCount(BiTree T); //统计二叉树中叶子结点的个数
void InitBiTree(BiTree &T)
{
T=NULL;
}
void DestroyBiTree(BiTree &T)
{
if(T){ //非空树
DestroyBiTree(T->lchild); //递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); //递归销毁右子树，如无右子树，则不执行任何操作
free(T); //释放根节点
T=NULL; //空指针赋值
}
}
void PreOrderTraverse(BiTree T)//先序递归遍历T
{
if(T)
{
printf("%d",T->data); //先访问根节点
PreOrderTraverse(T->lchild); //再先序遍历左子树
PreOrderTraverse(T->rchild); //最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T)//中序递归遍历T
{
if(T)
{
InOrderTraverse(T->lchild); //先遍历左子树
printf("%d",T->data); //在访问根节点
InOrderTraverse(T->rchild); //最后遍历右子树
}
}
void PostOrderTraverse(BiTree T)
{
if(T)
{
PostOrderTraverse(T->lchild); //先遍历左子树
PostOrderTraverse(T->rchild); //再遍历右子树
printf("%d",T->data); //在访问根节点
}
}
Status BiTreeEmpty(BiTree T)
{
if(T)
return FLASE;
else
return TRUE;
}
int BiTreeDepth(BiTree T)
{
int i,j;
if(!T)
return 0;//树的深度为0
i=BiTreeDepth(T->lchild); //i为左子树的深度
j=BiTreeDepth(T->rchild); //j为右子树的深度
return i>j?i+1:j+1; //T的深度为其左右子树的深度中的大者+1
}
TElemType Root(BiTree T)//返回T的根
{
if(BiTreeEmpty(T)) //二叉树为空
return 0;
else
return T->data;
}
void ExChangeTree(BiTree &T)
{//构造函数，使用递归算法进行左右结点转换
BiTree temp;
if(T!=NULL){//判断T是否为空，非空进行转换，否则不转换
temp=T->lchild;
T->lchild=T->rchild;//直接交换节点地址
T->rchild=temp;
ExChangeTree(T->lchild);
ExChangeTree(T->rchild);
}
}
int LeafCount(BiTree T)
{//统计二叉树中叶子结点的个数
if(!T) return 0;
if(!T->lchild &&!T->rchild){//如果二叉树左子树和右子树皆为空,说明该二叉树根节点为叶子节点,加1.
return 1;
}else{
return LeafCount(T->lchild)+LeafCount(T->rchild);
}
}
void PrintAllPath(BiTree T, char path[], int pathlen)
{//二叉树中从每个叶子结点到根结点的路径
int i;
if(T != NULL) {
path[pathlen] = T->data; //将当前结点放入路径中
if(T->lchild == NULL && T->rchild == NULL) {//叶子结点
for(i = pathlen; i >= 0; i--)
printf("%d ",path[i]);
printf("\n");
}else{
PrintAllPath(T->lchild, path, pathlen + 1);
PrintAllPath(T->rchild, path, pathlen + 1);
}
}
}
TElemType Value(BiTree p) //二叉树T存在，p指向T中的某个结点，结果返回p所指的结点
{
return p->data;
}
void Assign(BiTree p,TElemType value)
{
p->data=value;
}
void CreateBiTree(BiTree &T) //按照先序次序输入二叉树中结点的值
{
TElemType ch;
scanf("%d",&ch);
if(ch==0) //当输入的值为0的时候结点的值为空
T=NULL;
else //结点值不为空
{
T=(BiTree)malloc(sizeof(BiTNode)); //生成根节点
if(!T)
exit(0);
T->data=ch;
CreateBiTree(T->lchild); //递归构造左子树
CreateBiTree(T->rchild); //递归构造右子树
}
}
int main()
{
BiTree T;
TElemType e1;
InitBiTree(T); //初始化二叉树T
cout<<"构造二叉树后,树是否为空?(1:是 0:否) 树的深度"<<BiTreeEmpty(T)<<BiTreeDepth(T)<<endl;
e1=Root(T);
if(e1!=0)
cout<<"二叉树的根是"<<e1<<endl;
else
cout<<"无根"<<endl;
CreateBiTree(T);
cout<<"建立二叉树后,树是否为空?(1:是 0:否) 树的深度"<<BiTreeEmpty(T)<<BiTreeDepth(T)<<endl;
e1=Root(T);
if(e1!=0)
cout<<"二叉树的根是"<<e1<<endl;
else
cout<<"无根"<<endl;
cout<<"先序遍历递归二叉树:";
PreOrderTraverse(T);cout<<endl;
cout<<"中序遍历递归二叉树:";
InOrderTraverse(T);cout<<endl;
cout<<"后序遍历递归二叉树";
PostOrderTraverse(T);cout<<endl;
int e2=LeafCount(T);
cout<<"叶子结点数为"<<e2<<endl;
cout<<endl<<"二叉树中从每个叶子结点到根结点的所有路径：";
char path[256];
int pathlen=0;
PrintAllPath(T,path,pathlen);//
ExChangeTree(T);
cout<<"交换左右子树之后输出先序遍历的结果";
PreOrderTraverse(T);
return 0;
}
