[C++知识库]C语言 ，数据结构--二叉树，初步解释与实现

二叉树：可以非常形象的理解为一颗只有两个树枝的树。

? ? ? ? ? ? ? 转化为图形解释，就是一个圆圈只有两个两个圆圈和自身有关系，并且有直线和其链接。

? ? ? ? ? ? ? 转化为代码实现就是，一个节点，只携带两个指针，这两个指针分别指向一个节点。

（一）.【存储结构描述】

//构造二叉树结点
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("%c\t",T->data);
????????PreOrderTraverse(T->lchild);
????????PreOrderTraverse(T->rchild);
????}
}

3.中序遍历（左，根，右）

//使用递归算法对二叉树进行?中序遍历(左?根?右)
void??InOerderTraverse(BiTree?T){
????if?(T)
????{
????????InOerderTraverse(T->lchild);
????????printf("%c\t",T->data);
????????InOerderTraverse(T->rchild);
????}
}

4.后序遍历（左，右，根）

//使用递归算法对二叉树进行?后序遍历?(左?右?根)
void??PostOrderTraverse(BiTree?T){
????if(T){
?????????PostOrderTraverse(T->lchild);
?????????PostOrderTraverse(T->rchild);
?????????printf("%c\t",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("二叉树中的叶子节点的个数：%d\n",LeafNodeCount(B));
????printf("二叉树中的度为1的节点的个数：%d\n",CountNode1(B));
????printf("二叉树中的度为2的节点的个数：%d\n",CountNode2(B));
}

10.结果实现

?