二叉树的定义与性质

枫桥2026/6/29大约 4 分钟

复习定位

二叉树是最基础的树形数据结构——每个结点最多有两个子结点(左孩子和右孩子)。树可以用递归定义——一棵树是根结点加上若干棵不相交的子树。二叉树的相关性质(叶子结点数=度为2的结点数+1、第k层最多2^{k-1}个结点)是选择题高频考点。

二叉树的定义

二叉树是n(n≥0)个结点的有限集合——要么是空树(n=0)或称空二叉树——要么由一个根结点和两棵互不相交的树组成——分别叫作左子树和右子树。左子树和右子树也各是一棵二叉树。

注意二叉树的"左"和"右"是有顺序的——交换左右子树得到另一棵二叉树。

满二叉树——一棵深度为h且有$2^{h-1$个结点的二叉树。每一层的结点数达到最大——第k层有$2}$个结点。满二叉树的结点编号规则很方便——从根开始编号1、2...依次从左到右、从上到下——编号i的结点的左孩子=2i(如果2i≤n)、右孩子=2i+1(如果2i+1≤n)。

完全二叉树——一棵深度为h的二叉树——除了第h层外其他各层的结点数都达到最大——且第h层的结点全部集中在最左侧。完全二叉树可以用数组(顺序表)进行紧凑的存储——不需要指针链接——通过编号计算父子关系。堆排序的堆就是完全二叉树——在数组中存储。

二叉排序树/二叉搜索树——左子树所有结点的关键字≤根≤右子树所有结点。查找时——比较关键字决定左走或右走——每个步排除一半的范围——平均O(log n)。

平衡二叉树(AVL)——任意结点的左右子树高度差的绝对值不超过1。平衡二叉树保证查找的高效(最坏O(log n))——不会退化成链表。

$n_0=n_2+1$的证明：总边数=n-1(除根外每个结点有一个入边)——度贡献边数= $n_1+2n_2$(度为1贡献1条出边、度为2贡献2条)。所以n-1 = n_1+2n_2——又n=n_0+n_1+n_2——联合消去n_1→ n_0=n_2+1。

顺序存储——使用一个一维数组存放完全二叉树——结点编号i存储在数组下标i-1(或i)的位置。可方便地从编号i推出父结点(i/2)和子结点(2i,2i+1)。非完全二叉树用顺序存储会浪费大量空间(数组上空位的空洞)。

链式存储——每个结点包含：

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

每个结点占用data + 两个指针(共20+字节)——空间使用灵活——但n个结点有n+1个空指针域(指向NULL)。

二叉树的第k层最多几个结点？如果只有4层——总的最多结点数是多少——用公式$2^h-1$计算的数值是多少？
一棵完全二叉树有500个结点——求叶子结点个数、度为1的结点数、度为2的结点数？(可以从$n_0=n_2+1$和$n=n_0+n_1+n_2$联合求解——完全二叉树的n_1要么为0要么为1)
一棵二叉树叶子数为$n_0$、度为2的节点数为$n_2$——为什么任意二叉树都有$n_0=n_2+1$——用边数和结点数的关系推导。
顺序存储(数组)用于完全二叉树比链式存储更节省空间是吗——非完全二叉树用顺序存储的空间浪费多大情况？举一个极端例子：深度为10但每个内部结点只有右孩子的二叉树——使用顺序存储需要多大的数组？
二叉搜索树的中序遍历结果是增序序列——为什么？证明这个性质。