二叉树（Binary tree）是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树，且有左右之分。
#include
#include
#include
#define OK 1
#define ERROR 0
#include
using namespace std;
typedef struct BiTode{
char data;
struct BiTode *lchild,*rchild;
}*BiTree;
int LeafCount=0;
int InitBiTree(BiTree &T);//建立一个空树
int DestroyBiTree(BiTree &T);//若树存在，销毁树
int CreateBiTree(BiTree &T);//若树存在，向其中加入数据
int PreOrderTraverse(BiTree T);//若树存在且不为空，先序遍历树
int InOrderTraverse(BiTree T);//若树存在且不为空，中序遍历树
int PostOrderTraverse(BiTree T);//若树存在且不为空，后序遍历树
int LDR(BiTree T);//采用非递归方法中序遍历二叉树
int BiTreeEmpty(BiTree T);//判断树为不为空，为空返回1，不空返回0
int Root(BiTree T);//若树存在，打印树的根
BiTree Parent(BiTree T,char e);//若树存在，且e不是根节点，返回它的双亲，否则返回空
int Depth(BiTree T);//若树存在，求树的深度
int LeafNum(BiTree T);//统计叶子结点的个数
int OperateMenu();//建立菜单，提示操作代码
int main()
{
BiTree T=NULL;
char ch;
BiTree t;
char ce;
printf("是否要进行操作？（继续输入Y或者y，否则结束）n");
scanf("%c",&ch);
while(ch=='Y'||ch=='y'){
switch(OperateMenu()){
case 1:
InitBiTree(T);
if(T!=NULL)printf("空树建立成功！");
break;
case 2:
if(BiTreeEmpty(T))break;
getchar();
printf("请输入数据：n");
CreateBiTree(T);
printf("输入成功！");
break;
case 3:
if(BiTreeEmpty(T))break;
printf("先序遍历二叉树的结果为：");
PreOrderTraverse(T);
break;
case 4:
if(BiTreeEmpty(T))break;
printf("中序遍历二叉树的结果为：");
InOrderTraverse(T);
break;
case 5:
if(BiTreeEmpty(T))break;
printf("后序遍历二叉树的结果为：");
PostOrderTraverse(T);
break;
case 6:
if(BiTreeEmpty(T))break;
DestroyBiTree(T);
if(T==NULL)printf("销毁成功！n");
break;
case 7:
if(BiTreeEmpty(T))break;
printf("树的深度为%dn",Depth(T));
break;
case 8:
if(BiTreeEmpty(T))break;
LeafNum(T);
printf("叶子结点个数为：%d",LeafCount);
break;
case 9:
if(BiTreeEmpty(T))break;
printf("遍历结果为");
LDR(T);
break;
case 10:
if(BiTreeEmpty(T))break;
Root(T);
break;
case 11:
if(BiTreeEmpty(T))break;
printf("输入需要查找的元素：");
getchar();
scanf("%c",&ce);
t=Parent(T,ce);
printf("双亲为%c",t->data);
break;
}
printf("n是否还要继续操作？（继续输入Y或者y，否则结束）n");
getchar();
scanf("%c",&ch);
}
}
int InitBiTree(BiTree &T){//建立一个空树
T=(BiTode*)malloc(sizeof(BiTree));
return OK;
}
int CreateBiTree(BiTree &T){//若树存在，向其中加入数据
//按先序次序输入二叉树的值，用#号代表空树
char c;
scanf("%c",&c);
if(c=='#'){T=NULL;return 0;}
else{
T=(BiTode*)malloc(sizeof(BiTode));
if(!T)exit (-1);
T->data=c;//生成根节点
CreateBiTree(T->lchild);//构造左子树
CreateBiTree(T->rchild);//构造右子树
}
return OK;
}
int PreOrderTraverse(BiTree T){//若树存在且不为空，先序遍历树{
if(T!=NULL){
printf("%c",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
return OK;
}
int PostOrderTraverse(BiTree T){//若树存在且不为空，后序遍历树
if(T!=NULL){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c",T->data);
}
return OK;
}
int InOrderTraverse(BiTree T){//若树存在且不为空，中序遍历树
if(T!=NULL){
InOrderTraverse(T->lchild);
printf("%c",T->data);
InOrderTraverse(T->rchild);
}
return OK;
}
int DestroyBiTree(BiTree &T){//若树存在，销毁树
if(T!=NULL){
DestroyBiTree(T->lchild);
free(T);
DestroyBiTree(T->rchild);
}
T=NULL;
return OK;
}
int Depth(BiTree T)//若树存在，求树的深度
{
if(T)
{
int m=Depth(T->lchild);
int n=Depth(T->rchild);
if(m>n)
{
return (m+1);
}
else
{
return (n+1);
}
}
return 0;
}
int LeafNum(BiTree T){//统计叶子结点的个数
if(T!=NULL){
if(T->lchild==NULL&&T->rchild==NULL)LeafCount++;
LeafNum(T->lchild);
LeafNum(T->rchild);
}
return OK;
}
int LDR(BiTree T){//采用非递归方法中序遍历二叉树
stack
BiTree p;
S.push(T);//根指针进栈
while(!S.empty()){
p=S.top();
while(p!=NULL){S.push(p->lchild);p=S.top();}//向左走到头
S.pop();
if(!S.empty()){
p=S.top();
if(!p)return ERROR;
S.pop();
printf("%c",p->data);
S.push(p->rchild);
}
}
return OK;
}
int BiTreeEmpty(BiTree T){//判断树为不为空，为空返回1，不空返回0
if(T==NULL){
printf("请先建树！n");
return 1;
}
else return 0;
}
int Root(BiTree T){//若树存在，打印树的根
if(T)printf("树根为%c",T->data);
return OK;
}
BiTree Parent(BiTree T,char ce){//若树存在，且e不是根节点，返回它的双亲，否则返回空
stack
BiTree p;
S.push(T);//根指针进栈
while(!S.empty()){
p=S.top();
while(p!=NULL){S.push(p->lchild);p=S.top();}//向左走到头
S.pop();
if(!S.empty()){
p=S.top();
S.pop();
if(p->lchild->data==ce||p->rchild->data==ce)return p;
S.push(p->rchild);
}
}
return NULL;
}
int OperateMenu(){//建立菜单，提示操作代码
int num;
printf("--------------------------------------------------------------------n");
printf("1：建立空树！t2：向树中添加数据！t3：先序遍历树！n4：中序遍历树！t5：后序遍历树！t 6：销毁树 ！n7：求树的深度！t8：统计叶子结点个数！t9：采用非递归方式中序遍历树 ！n10：打印树根！t11：获得孩子的双亲！tn");//提供菜单选项
printf("--------------------------------------------------------------------n");
scanf("%d",&num);
for(int i=0;;i++){
if(num<1||num>11){printf("选择错误！");return -1;}
else if(num==1){return num;break;}
else if(num==2){return num;break;}
else if(num==3){return num;break;}
else if(num==4){return num;break;}
else if(num==5){return num;break;}
else if(num==6){return num;break;}
else if(num==7){return num;break;}
else if(num==8){return num;break;}
else if(num==9){return num;break;}
else if(num==10){return num;break;}
else if(num==11){return num;break;}
}
}
- 建立一个空树
2.向树中添加数据（ABC##DE#G##F### #代表NULL）
3.先序遍历二叉树并打印
4.中序遍历二叉树并打印
5.后序遍历二叉树并打印
6.采用非递归方式中序遍历二叉树并打印
7.计算二叉树的深度
8.统计叶子结点的个数
9.打印二叉树的树根
10.销毁二叉树
