#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
typedef char t; //定义数据类型
typedef struct BinaryTreeNode
{
t Data;
struct BinaryTreeNode *LChlid,*RChlid;
}BinaryTreeNode,* BinTree; //建立二叉树链式存储
BinaryTreeNode *PreCreateBt( ) //先序建立二叉树
{
char ch;
BinTree t;
ch=getchar();
if(ch==’#’) //输入时用#表述为空
t=NULL;
else{
t = (BinTree *)malloc(sizeof(BinaryTreeNode));
t->Data = ch;
t->LChlid =PreCreateBt();
t->RChlid =PreCreateBt();
}
return t; //返回根节点
}
void PreOrderTransverse(BinTree t) //先序遍历
{
if(t==NULL)
return;
printf(“%c”,t->Data);
PreOrderTransverse(t->LChlid);
PreOrderTransverse(t->RChlid);
}
void InOrderTransverse(BinTree t) //中序遍历
{
if(t==NULL)
return;
else
{
InOrderTransverse(t->LChlid);
printf(“%c”,t->Data);
InOrderTransverse(t->RChlid);
}
}
void PostOrderTransverse(BinTree t) //后序遍历
{
if(t==NULL)
return;
PostOrderTransverse(t->LChlid);
PostOrderTransverse(t->RChlid);
printf(“%c”,t->Data);
}
int Count(BinTree t) //全部结点个数
{
if(t==NULL)
return 0; //空二叉树结点数为0
else //左右子树结点总数加1
return Count(t->LChlid)+Count(t->RChlid)+1;
}
int leafCount(BinTree t) //叶子结点个数
{
if(t== NULL)
{
return 0;
}
if ((t->LChlid==NULL) && (t->RChlid==NULL))
{
return 1;
}
return leafCount(t->LChlid)+leafCount(t->RChlid);
}
int High(BinTree t) //二叉树深度
{
int h;
if(t==NULL)
h=0;
else
{
int h1,h2;
h1= High(t->LChlid);
h2=High(t->RChlid,h2);
if(h1>=h2)
{
h=h1;
}
else
{
h=h2;
}
h=h+1;
}
return h;
}
void SwapChildren(BinTree t) //二叉树交换左右子树
{
int temp;
temp = (BinTree *)malloc(sizeof(BinaryTreeNode));
if(t==NULL)
return;
temp = t->LChlid;
t->LChlid=t->RChlid;
t->RChlid = temp;
SwapChildren(t->LChlid);
SwapChildren(t->RChlid);
printf(“%c”,t->Data);
}
void main()
{
BinTree t;
t=PreCreateBt();
printf(“先序遍历二叉树：”); //功能性的介绍，可以去掉，不影响结果
PreOrderTransverse(t);
printf(“\n”);
printf(“中序遍历二叉树：”);
InOrderTransverse(t);
printf(“\n”);
printf(“后序遍历二叉树：”);
PostOrderTransverse(t);
printf(“\n”);
printf(“二叉树结点总数:”);
printf(“%d\n”,Count(t));
printf(“叶子节点的个数:”);
printf(“%d\n”,leafCount(t));
printf(“树的高度:%d\n”,High(t));
printf(“二叉树交换左右子树:”);
SwapChildren(t);
printf(“\n”);
比如建立最简单的二叉树根结点为B、左子树为A、右子树为C，运算结果如图
输入时要注意二叉树建立的时候使用的是先序建立所以输入的时候要保证使用先序输入否则就会出错
