二叉树：可以非常形象的理解为一颗只有两个树枝的树。
转化为图形解释，就是一个圆圈只有两个两个圆圈和自身有关系，并且有直线和其链接。
转化为代码实现就是，一个节点，只携带两个指针，这两个指针分别指向一个节点。
（一）.【存储结构描述】
//构造二叉树结点
typedef struct node
{
DataType data;
struct node *lchild,*rchild;
}BiTNode,*BiTree;
（二）.【基本操作】
1.建立二叉链表
//完全二叉树的层次顺序依次输入结点信息建立二叉链表
BiTree CreateBinTree(BiTree &bt,char *t){
BiTree Q[MAXSIZE],s;
int front=1,rear=0,i=0;
char ch;//接受输入
ch=t[i];
i++;
bt=NULL;
while (ch!='#')
{
s=NULL;
if (ch!='@')
{
s=(BiTree)malloc(sizeof(BiTNode));
s->data=ch;
s->lchild=s->rchild=NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
bt=s;
else{
if (s&&Q[front])
if (rear%2==0)
Q[front]->lchild=s;
else
Q[front]->rchild=s;
if(rear%2==1)
front++;
}
ch=t[i];i++;
}
return bt;
}
2.前序遍历（根，左，右）
//使用递归算法对二叉树进行前序遍历(根 左 右)
void PreOrderTraverse(BiTree T){
if (T)
{
printf("%ct",T->data);
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}
3.中序遍历（左，根，右）
//使用递归算法对二叉树进行 中序遍历(左 根 右)
void InOerderTraverse(BiTree T){
if (T)
{
InOerderTraverse(T->lchild);
printf("%ct",T->data);
InOerderTraverse(T->rchild);
}
}
4.后序遍历（左，右，根）
//使用递归算法对二叉树进行 后序遍历 (左 右 根)
void PostOrderTraverse(BiTree T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%ct",T->data);
}
}
5.统计二叉树中叶子节点的个数
//统计二叉树中叶子结点的个数
int LeafNodeCount(BiTree T){
if(!T) return 0;
else if(!T->lchild&&!T->rchild) return 1;
else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild);
}
6.统计二叉树中度为 1 的节点
//统计二叉树中度为 1 的节点
int CountNode1(BiTree T){
if(!T||(!T->lchild&&!T->rchild)) return 0;
else if(T->lchild&&T->rchild) return CountNode1(T->lchild)+CountNode1(T->rchild);
else return CountNode1(T->lchild)+CountNode1(T->rchild)+1;
}
7.统计二叉树中度 为 2 的节点
//统计二叉树中度为 2 的节点
int CountNode2(BiTree T){
if(!T||(!T->lchild&&!T->rchild)) return 0;
else if(T->lchild&&T->rchild) return CountNode2(T->lchild)+CountNode2(T->rchild)+1;
else return CountNode2(T->lchild)+CountNode2(T->rchild);
}
8.主函数调用 与实现
int main(){
BiTree B;
char s3[13]={'H','A','B','C','J','D','@','@','E','@','@','F','#'};
printf("n按完全二叉树的层次顺序依次输入结点信息建立二叉链表（HABCJD@@@@EF#）n");
B=CreateBinTree(B,s3);
printf("n使用递归算法分别进行前、中、后序遍历n");
PreOrderTraverse(B);printf("n");
InOerderTraverse(B);printf("n");
PostOrderTraverse(B);printf("n");
printf("二叉树中的叶子节点的个数：%dn",LeafNodeCount(B));
printf("二叉树中的度为1的节点的个数：%dn",CountNode1(B));
printf("二叉树中的度为2的节点的个数：%dn",CountNode2(B));
}
10.结果实现
