/*
1、建立二叉树
2、三种遍历
3、节点的统计
4、是统计度分别为0,1,2的节点个数？
*/
#include<iostream.h>
#define N 10
struct Btree{
int date;
Btree *lchild;
Btree *rchild;
};
/*-----------------------------------------------------------------------------------*/
Btree *creat_B(int A[], Btree *K[], int n ) //建立二叉树
{
int i;
Btree *s;
for (i=0; i<n; i++) //把A数组中每一个数存入数数组K的date中
{
if (A[i]>0)
{
s=new Btree;
s->date=A[i];
s->lchild=NULL; //xian先把左子树，右子树置空
s->rchild=NULL;
K[i]=s;
}
}
for (i=0; i<n; i++)
{
if (A[0]>0) //判断A[i]以及下标，判断左右子树
{
if (A[i*2+1]>0 && (i*2+1)<n) K[i]->lchild=K[i*2+1];
if (A[i*2+2]>0 && (i*2+2)<n) K[i]->rchild=K[i*2+2];
}
}
return K[0]; //返回根结点
}
int x=0;//用于存放结点个数
void node_B(Btree *t)//统计节点个数
{
if(t!=NULL)
{
x++;
node_B(t->lchild);
node_B(t->rchild);
}
}
int x0=0;//度为0的节点个数
void node_0(Btree *t)//统计度为0的节点个数
{
if(t!=NULL)
{
//if(t->lchild==NULL&&t->rchild==NULL) x0++;
node_0(t->lchild);
node_0(t->rchild);
if(t->lchild==NULL&&t->rchild==NULL) x0++;
}//左右子树全是空
}
int x1=0;//存放度为1的节点个数
void node_1(Btree *t)//统计度为1的节点个数
{
if(t!=NULL)
{
node_1(t->lchild);
node_1(t->rchild);
if(t->lchild!=NULL&&t->rchild==NULL) x1++; //左右子树只能有一个
if(t->lchild==NULL&&t->rchild!=NULL) x1++;
}
}
int x2=0;//存放度为2的节点个数
void node_2(Btree *t)//统计度为2的节点个数
{
if(t!=NULL)
{
node_2(t->lchild);
node_2(t->rchild);
if(t->lchild!=NULL&&t->rchild!=NULL) x2++;//左右子树全不为空
}
}
/*-----------------------------------------------------------------------------------*/
/*
关键你要自己想明白递归是怎么回事，搞明白递归，那么一切二叉树问题都不是问题
*/
void preorder(Btree *t) //这是先序遍历二叉树，采用了递归的方法。
{
if(t!=NULL)
{
cout<<t->date<<" ";
preorder(t->lchild);
preorder(t->rchild);
}
}
void inorder(Btree *t) //这是中序遍历二叉树，采用了递归的方法。
{
if(t!=NULL)
{
inorder(t->lchild);
cout<<t->date<<" ";
inorder(t->rchild);
}
}
void postorder(Btree *t) //这是后序遍历二叉树，采用了递归的方法。
{
if(t!=NULL)
{
postorder(t->lchild);
postorder(t->rchild);
cout<<t->date<<" ";
}
}
main()
{
int a[N]={12,2,3,0,4,9,6,0,0,5}; //数值为0表示该下标对应的结点不存在
Btree *p,*bt[N];
p=creat_B(a,bt,N);//二叉树p建好了
cout<<"先序遍历："; //先序遍历输出
preorder(p);
cout<<endl;
cout<<"中序遍历："; //中序遍历输出
inorder(p);
cout<<endl;
cout<<"后序遍历：";//后序遍历输出
postorder(p);
cout<<endl;
node_B(p);
cout<<"二叉树的节点个数为："<<x<<endl;
node_0(p);
cout<<"度为0的节点个数："<<x0<<endl;
node_1(p);
cout<<"度为0的节点个数："<<x1<<endl;
node_2(p);
cout<<"度为0的节点个数："<<x2<<endl;
}