掌握二叉树的性质、顺序与链式存储、遍历和重建方法,并理解线索二叉树、二叉搜索树、平衡树与堆的结构特征。

# 一、二叉树的定义与性质

二叉树是由一个根结点和两棵互不相交的二叉树组成的有序树,分别称为左子树和右子树。左右子树不能互换;每个结点至多有两个孩子,且 “没有左孩子、有右孩子” 与 “有左孩子、没有右孩子” 是不同结构。

若根位于第 11 层,则第 ii 层最多有 2i−12^{i-1} 个结点;高度为 hh 的二叉树最多有

1+2+⋯+2h−1=2h−11+2+\cdots+2^{h-1}=2^h-1

个结点。这里高度按层数计,根在第 11 层。

满二叉树的每一层都填满,高度为 hh 时结点数是 2h−12^h-1。完全二叉树除最后一层外均填满,最后一层结点从左向右连续排列。若完全二叉树有 nn 个结点、高度为 hh(按层计),则

2h−1≤n≤2h−1,h=⌈log⁡2(n+1)⌉.2^{h-1}\le n\le2^h-1,\qquad h=\lceil\log_2(n+1)\rceil.

设 n0,n1,n2n_0,n_1,n_2 分别为度数为 0,1,20,1,2 的结点数。二叉树边数既等于 n0+n1+n2−1n_0+n_1+n_2-1,也等于 n1+2n2n_1+2n_2,故

n0=n2+1.\boxed{n_0=n_2+1}.

有些资料把 “每个内部结点有两个孩子” 的树称为严格或正则二叉树,把每层填满的树称为完美二叉树。本文使用数据结构课程常用的 “满二叉树” 表示各层均满;碰到不同资料时应依定义作答。

左右单支二叉树的区别、满二叉树与完全二叉树的形态,以及叶结点数与双分支结点数的关系

# 二、二叉树的存储结构

# 1. 顺序存储

完全二叉树适合用数组按层序存储。采用从 00 开始的数组下标时,结点 ii 的关系为

left⁡(i)=2i+1,right⁡(i)=2i+2,parent⁡(i)=⌊i−12⌋.\operatorname{left}(i)=2i+1,\quad \operatorname{right}(i)=2i+2,\quad \operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor.

若使用从 11 开始的下标,则左右孩子分别为 2i2i、2i+12i+1,双亲为 ⌊i/2⌋\lfloor i/2\rfloor。一般形状的二叉树使用顺序存储可能在缺失孩子处留下许多空位;完全二叉树或堆则不会产生大量空洞。

# 2. 链式存储

链式存储为每个结点保存数据、左孩子指针和右孩子指针,适用于任意形状的二叉树。

1
2
3
4
5
typedef struct BiTNode {
int data;
struct BiTNode *left;
struct BiTNode *right;
} BiTNode;

同一棵稀疏二叉树的链式结点指针和零起始顺序存储数组

# 三、二叉树遍历

遍历是按某种次序访问每个结点且恰好一次。先序、中序、后序的区别只在访问根结点的时机。

遍历访问顺序
先序根、左子树、右子树
中序左子树、根、右子树
后序左子树、右子树、根
层序按层从左到右,使用队列

同一棵二叉树的先序、中序、后序与层序遍历次序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void PreOrder(BiTNode *root) {
if (root == NULL) {
return;
}
Visit(root);
PreOrder(root->left);
PreOrder(root->right);
}

void InOrder(BiTNode *root) {
if (root == NULL) {
return;
}
InOrder(root->left);
Visit(root);
InOrder(root->right);
}

void PostOrder(BiTNode *root) {
if (root == NULL) {
return;
}
PostOrder(root->left);
PostOrder(root->right);
Visit(root);
}

三种深度优先递归遍历都访问 nn 个结点,时间复杂度为 O(n)O(n);递归栈空间为 O(h)O(h),其中 hh 为树高。退化成单支树时 h=nh=n。层序遍历使用队列,最坏需要 O(n)O(n) 辅助空间。

先序序列可用于复制或输出树形结构;中序序列在二叉搜索树中为递增序列;后序序列适合先处理子结点再处理父结点,例如释放整棵树或计算表达式。

# 四、由遍历序列构造二叉树

若结点值互不相同,先序序列与中序序列能唯一确定一棵二叉树:

  1. 先序序列首元素是根。
  2. 在中序序列中找到根,左侧元素构成左子树,右侧元素构成右子树。
  3. 按左子树结点数,将先序序列余下部分拆成左、右子树的先序序列,再递归构造。

中序加后序也能唯一确定二叉树,区别是后序末元素为根。先序加后序一般不能唯一确定,因为单孩子结点无法判断孩子位于左边还是右边;若额外保证每个内部结点都有两个孩子,则可唯一重建。

以下图例使用先序序列 A B D C E 和中序序列 B D A C E 。先序首项 A 是根;在中序序列中, A 左侧的 B D 与右侧的 C E 分别属于左右子树,再按子树结点数递归切分先序序列。

根据先序序列 A B D C E 和中序序列 B D A C E 逐步划分左右子树并重建二叉树

# 五、线索二叉树

链式二叉树有 nn 个结点时共有 2n2n 个左右指针域,其中只有 n−1n-1 个指向非空孩子,另有 n+1n+1 个空链域。线索二叉树利用空链域存放遍历序列中的前驱或后继信息。

若以中序遍历建立线索,结点的空左指针可指向其中序前驱,空右指针可指向其中序后继。结点还需用标志位区分该指针是孩子链接还是线索。线索化不改变遍历次序,可在不递归、不使用栈的情况下寻找中序前驱或后继。

中序线索二叉树中结点 C 的空左指针指向前驱 B、空右指针指向后继 D

# 六、二叉搜索树与平衡树

二叉搜索树(BST)满足:左子树所有关键字小于根,右子树所有关键字大于根,且左右子树也分别为二叉搜索树。中序遍历因此得到递增序列。查找、插入、删除的代价与树高 hh 成正比:接近平衡时为 O(log⁡n)O(\log n),按有序关键字依次插入时会退化到 O(n)O(n)。

AVL 树通过限制每个结点左右子树高度差来保持平衡。定义平衡因子为左子树高度减右子树高度,AVL 要求其属于 {−1,0,1}\{-1,0,1\}。插入后失衡时,根据失衡结点和较高子树的方向,使用 LL、RR 单旋或 LR、RL 双旋恢复平衡,查找、插入和删除均为 O(log⁡n)O(\log n)。

红黑树以结点颜色和路径黑高约束控制树高,平衡条件比 AVL 宽松,插入和删除通常调整次数更少;其高度仍为 O(log⁡n)O(\log n)。考题若要求具体旋转过程,应按题目给定的插入或删除规则逐步模拟。

# 七、堆与二叉树应用

堆是满足堆序性质的完全二叉树。大根堆的每个结点都不小于其孩子,小根堆则不大于其孩子。堆适合用数组顺序存储,可在 O(1)O(1) 时间读取堆顶,并在 O(log⁡n)O(\log n) 时间插入或删除堆顶。堆排序和树搜索的细节分别在排序、查找笔记中展开。

二叉搜索树查找路径、AVL 左左失衡后的右旋以及大根堆和层序数组

# 八、考场检查清单

  1. 左右子树是有序的;只有一个孩子时,孩子位于左或右会形成不同二叉树。
  2. 完全二叉树的数组下标公式依赖从 00 还是从 11 开始。
  3. 二叉树的叶子数满足 n0=n2+1n_0=n_2+1。
  4. 先序加中序、后序加中序在结点值互异时可唯一确定;先序加后序一般不行。
  5. BST 操作取决于树高,只有保持平衡才能保证对数级代价。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝