完全二叉树知道叶子结点

### 完全二叉树中的叶子结点特性

在完全二叉树中，除了最后一层外，其它各层的节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的位置上。如果存在度为1的节点，则只可能有一个这样的节点，而且这个节点只有左子树而没有右子树。

对于完全二叉树而言，其叶子结点具有如下特点：

- **位置分布**：所有叶子结点仅出现在最后两层；其中倒数第二层上的任何叶子结点一定位于整棵树左侧部分。

- **数量关系**：设n表示总节点数目，m代表叶节点的数量，在理想情况下（即满二叉树），满足\( m=\lceil n/2 \rceil \)[^1]。

为了更好地理解这些性质以及如何通过编程实现对这类特殊形式二叉树的操作，可以考虑以下C++代码片段来展示怎样构建并计算给定字符串所描述的一棵完全二叉树里有多少个叶子结点。

#include <iostream>
using namespace std;

typedef struct BiTNode {
    char data;
    struct BiTNode* lchild, * rchild;
} BiTNode, *BiTree;

// 构建函数省略...

int LeafCount(BiTree T){
    static int count = 0; // 使用静态变量保存计数值
    if (T != NULL) {
        LeafCount(T->lchild);
        LeafCount(T->rchild);
        if (!T->lchild && !T->rchild)// 判断是否为叶子结点
            ++count;
    }
    return count;
}

上述程序定义了一个用于处理二叉树的数据结构`BiTNode`及其对应的指针类型`BiTree`。接着实现了名为`LeafCount()`的方法用来递归地遍历整个树形结构，每当发现一个既无左也无右孩子的节点时便增加全局计数器`count`一次。最终返回的就是这棵树内所有的叶子总数目[^2]。

值得注意的是，这段代码适用于任意形态的二叉树，但对于特定类型的如完全二叉树来说同样有效。