7.1 二叉树¶
二叉树(binary tree)是一种非线性数据结构,代表“祖先”与“后代”之间的派生关系,体现了“一分为二”的分治逻辑。与链表类似,二叉树的基本单元是节点,每个节点包含值、左子节点引用和右子节点引用。
/* 二叉树节点类 */
class TreeNode {
val: number;
left: TreeNode | null;
right: TreeNode | null;
constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
this.val = val === undefined ? 0 : val; // 节点值
this.left = left === undefined ? null : left; // 左子节点引用
this.right = right === undefined ? null : right; // 右子节点引用
}
}
use std::rc::Rc;
use std::cell::RefCell;
/* 二叉树节点结构体 */
struct TreeNode {
val: i32, // 节点值
left: Option<Rc<RefCell<TreeNode>>>, // 左子节点引用
right: Option<Rc<RefCell<TreeNode>>>, // 右子节点引用
}
impl TreeNode {
/* 构造方法 */
fn new(val: i32) -> Rc<RefCell<Self>> {
Rc::new(RefCell::new(Self {
val,
left: None,
right: None
}))
}
}
/* 二叉树节点结构体 */
typedef struct TreeNode {
int val; // 节点值
int height; // 节点高度
struct TreeNode *left; // 左子节点指针
struct TreeNode *right; // 右子节点指针
} TreeNode;
/* 构造函数 */
TreeNode *newTreeNode(int val) {
TreeNode *node;
node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = val;
node->height = 0;
node->left = NULL;
node->right = NULL;
return node;
}
每个节点都有两个引用(指针),分别指向左子节点(left-child node)和右子节点(right-child node),该节点被称为这两个子节点的父节点(parent node)。当给定一个二叉树的节点时,我们将该节点的左子节点及其以下节点形成的树称为该节点的左子树(left subtree),同理可得右子树(right subtree)。
在二叉树中,除叶节点外,其他所有节点都包含子节点和非空子树。如图 7-1 所示,如果将“节点 2”视为父节点,则其左子节点和右子节点分别是“节点 4”和“节点 5”,左子树是“节点 4 及其以下节点形成的树”,右子树是“节点 5 及其以下节点形成的树”。
图 7-1 父节点、子节点、子树
图解 7-1:二叉树的节点与子树
以根节点与左右分支为例,区分直接相连的单个子节点与包含其全部后代的子树。
这棵 4 层完美二叉树共有 15 个节点,根为 1,节点值按层从左到右依次为 1 至 15。底层节点 8 至 15 均为没有子节点的叶节点;节点 1 至 7 共 7 个非叶节点的左右子节点连接如下表。
图中用橙色区域圈出根 1 的左子树,用蓝色区域圈出右子树;区域包括各自的根及全部后代。
| 父节点 | 左子节点 | 右子节点 |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 4 | 5 |
| 3 | 6 | 7 |
| 4 | 8 | 9 |
| 5 | 10 | 11 |
| 6 | 12 | 13 |
| 7 | 14 | 15 |
以根节点 1 为参照,直接相连的左子节点是单个节点 2,右子节点是单个节点 3;而左子树是以 2 为根的整棵树,包含 2、4、5、8、9、10、11 共 7 个节点,右子树以 3 为根,包含 3、6、7、12、13、14、15 共 7 个节点。子树包含其根及全部后代,范围大于单个子节点。
父子与子树关系均相对所选参考节点而言:1 是 2、3 的父节点,2 又是 4、5 的父节点。图中把根 1 标作“父节点”仅表示它是 2、3 的父节点,根节点自身没有父节点。
7.1.1 二叉树常见术语¶
二叉树的常用术语如图 7-2 所示。
- 根节点(root node):位于二叉树顶层的节点,没有父节点。
- 叶节点(leaf node):没有子节点的节点,其两个指针均指向
None。 - 边(edge):连接两个节点的线段,即节点引用(指针)。
- 节点所在的层(level):从顶至底递增,根节点所在层为 1 。
- 节点的度(degree):节点的子节点的数量。在二叉树中,度的取值范围是 0、1、2 。
- 二叉树的高度(height):从根节点到最远叶节点所经过的边的数量。
- 节点的深度(depth):从根节点到该节点所经过的边的数量。
- 节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量。
图 7-2 二叉树的常用术语
图解 7-2:二叉树的根、叶、深度与高度
根、叶节点标注与两侧标尺,分别说明节点位置、深度和高度。
图中是一棵四层二叉树,绿色圆圈内为节点值,灰色箭头从父节点指向左、右子节点。顶层的 1 是根节点;1 的左、右子节点是 2、3;2 的左、右子节点是 4、5;3 的左、右子节点是 6、7;4 的左、右子节点是 8、9;6 只有左子节点 12;7 的左、右子节点是 14、15。
每条有向连线代表一条边。顶部的“根节点”标注指向最上方没有父节点的 1;底部的“叶节点”通过六条引线指向 8、9、5、12、14、15。这六个节点都没有子节点,其中 5 位于第 3 层,其余五个位于第 4 层,说明叶节点不必处在同一层。
标尺以水平虚线对齐各层,两侧标尺按经过的边数度量深度与高度:左侧上方标尺从根 1 量到节点 2,经过 1 条边,标明“节点 2 深度 = 1”;左侧下方标尺从节点 2 量到其最远叶节点 8、9,经过 2 条边,标明“节点 2 高度 = 2”。右侧长标尺从根 1 量到底层最远叶节点,经过 3 条边,标明“二叉树高度 = 3”。
节点 2 到叶节点 5 只经过 1 条边,到叶节点 8、9 则经过 2 条边;高度取最远叶节点的距离,因此取 2。四层树的高度是 3,层数与边数相差 1。
Tip
请注意,我们通常将“高度”和“深度”定义为“经过的边的数量”,但有些题目或教材可能会将其定义为“经过的节点的数量”。在这种情况下,高度和深度都需要加 1 。
7.1.2 二叉树基本操作¶
1. 初始化二叉树¶
与链表类似,首先初始化节点,然后构建引用(指针)。
// 初始化节点
let n1 = TreeNode::new(1);
let n2 = TreeNode::new(2);
let n3 = TreeNode::new(3);
let n4 = TreeNode::new(4);
let n5 = TreeNode::new(5);
// 构建节点之间的引用(指针)
n1.borrow_mut().left = Some(n2.clone());
n1.borrow_mut().right = Some(n3);
n2.borrow_mut().left = Some(n4);
n2.borrow_mut().right = Some(n5);
可视化运行
2. 插入与删除节点¶
与链表类似,在二叉树中插入与删除节点可以通过修改指针来实现。图 7-3 给出了一个示例。
图 7-3 在二叉树中插入与删除节点
图解 7-3:二叉树的插入与摘除
通过改连左子节点引用,在完整保留节点 2 子树的前提下插入或摘除中间节点 P。
初始根为 1(n1),左接 2(n2)、右接叶节点 3;2 左接叶节点 4、右接叶节点 5。待插入节点 P 的值为 0,左右均空。静态图从左到右为准备插入、插入完成、摘除完成三幅子图。
先用 n2 保存节点 2 的引用。左侧子图中 P 独立在树外;中间子图执行 n1.left = P、P.left = n2,左分支变为 1→P(0)→2,2 的子节点 4、5 均保留,P 的右子节点为空;右侧子图执行 n1.left = n2,绕过 P 恢复原树。根 1 的右子节点始终为 3。
摘除后恢复原树连接,仅能断言从根节点不再能到达 P,不能据此断言 P 的对象内存已被释放,也不表示删去了整棵左子树。
可视化运行
Tip
需要注意的是,插入节点可能会改变二叉树的原有逻辑结构,而删除节点通常意味着删除该节点及其所有子树。因此,在二叉树中,插入与删除通常是由一套操作配合完成的,以实现有实际意义的操作。
7.1.3 常见二叉树类型¶
1. 完美二叉树¶
如图 7-4 所示,完美二叉树(perfect binary tree)所有层的节点都被完全填满。在完美二叉树中,叶节点的度为 \(0\) ,其余所有节点的度都为 \(2\) ;若树的高度为 \(h\) ,则节点总数为 \(2^{h+1} - 1\) ,呈现标准的指数级关系,反映了自然界中常见的细胞分裂现象。
Tip
请注意,在中文社区中,完美二叉树常被称为满二叉树。
图 7-4 完美二叉树
图解 7-4:完美二叉树:每一层都完全填满
完美二叉树要求每一层全部填满,叶节点都在最底层。
左侧四层树的节点均无数值标签,节点数逐层翻倍:第一层有 1 个根节点;第二层有 2 个节点;第三层有 4 个节点;第四层有 8 个叶节点。树下方的灰色说明框写着“所有层的节点都被填满”。
图中每个非叶节点都同时拥有左、右两个子节点,全部 8 个叶节点都整齐排列在最底部的第四层。右侧标题标出“完美二叉树”、英文“perfect binary tree”,并注明“(也被称为满二叉树)”。
按图数得四层、15 个节点,按边数计算高度为 3;一般地,高度为 h 的完美二叉树共有 2 的(h+1)次方减 1 个节点。
2. 完全二叉树¶
如图 7-5 所示,完全二叉树(complete binary tree)仅允许最底层的节点不完全填满,且最底层的节点必须从左至右依次连续填充。请注意,完美二叉树也是一棵完全二叉树。
图 7-5 完全二叉树
图解 7-5:完全二叉树:末层从左到右连续填充
前三层全部填满,第四层从左起连续占满五个位置,仅最右侧三个位置留空。
左侧四层无数值标签的二叉树中,前三层全部填满,分别有 1、2、4 个节点。第三层从左往右数:第一、第二个节点各有左、右两个子节点;第三个节点只有左子节点;第四个节点没有子节点。因此第四层共有五个叶节点,连续占据最左侧的五个位置。
右侧标出“完全二叉树”与英文“complete binary tree”。树底部有一条指向左侧的长箭头,配合灰色说明框“最底层节点靠左填充,其他层节点全被填满”,强调末层节点必须紧靠左侧连续排列,中间不能出现空缺。
按图数得高度为 3、共 12 个节点,符合完全二叉树定义;因第四层右侧仍有三个空位未填满,它不是完美二叉树。
3. 完满二叉树¶
如图 7-6 所示,完满二叉树(full binary tree)除了叶节点之外,其余所有节点都有两个子节点。
图 7-6 完满二叉树
图解 7-6:完满二叉树:所有节点的度都为 0 或 2
完满二叉树约束每个节点的子节点数量,而不要求各层填满。
左侧四层树共 7 个无数值标签的节点。根的右子节点是叶节点;根的左子节点有左、右两个子节点,其中左侧是叶节点,右侧再分出两个叶节点。
节点的“度”即它拥有的子节点数量。右侧标出“完满二叉树(full binary tree)”,底部灰色说明框写着“所有节点的度都为 0 或 2”:图中三个非叶节点的度全为 2,4 个叶节点的度全为 0,不存在度为 1 的单子节点;4 个叶节点分散在第二、第三、第四层。
完满二叉树只要求每个节点有 0 个或 2 个子节点,不要求每一层填满或所有叶节点处于同一层。
4. 平衡二叉树¶
如图 7-7 所示,平衡二叉树(balanced binary tree)中任意节点的左子树和右子树的高度之差的绝对值不超过 1 。
图 7-7 平衡二叉树
图解 7-7:平衡二叉树:任意节点的左右子树高度差不超过 1
这棵树并不左右对称,却满足每个节点的平衡条件。
右侧说明框定义 d 为左子树高度减右子树高度,并要求每个节点的 |d| ≤ 1。d 是高度差,不是节点的度;按边数计高度时,叶节点为 0,空子树记为 −1。
左侧树有四层、8 个无数值标签的节点。根的左子节点只有一个左叶节点,右子树为空,旁标 d = 1。
根的右子节点有左、右两个子节点:左侧内部节点又带两个叶节点,右侧本身是叶节点。因此根的右子节点旁标 d = 1,它的左子节点旁标 d = 0。全部四个叶节点左右均为空,旁标 d = 0。
根的左子树高度为 1、右子树高度为 2,故根旁标 d = −1。其余节点的高度差也均不超过 1,整棵树满足平衡条件。
判定平衡要检查每个节点;只看根节点的高度差还不够。
7.1.4 二叉树的退化¶
图 7-8 展示了二叉树的理想结构与退化结构。当二叉树的每层节点都被填满时,达到“完美二叉树”;而当所有节点都偏向一侧时,二叉树退化为“链表”。
- 完美二叉树是理想情况,可以充分发挥二叉树“分治”的优势。
- 链表则是另一个极端,各项操作都变为线性操作,时间复杂度退化至 \(O(n)\) 。
图 7-8 二叉树的最佳结构与最差结构
图解 7-8:二叉树的最佳结构与链状退化结构
同样的七个节点,分叉或单侧相连会形成不同的树高。
左图下方标注“理想结构:完美二叉树”。根节点为 1;1 的左、右子节点为 2、3;2 的左、右子节点为 4、5;3 的左、右子节点为 6、7;底层 4、5、6、7 共 4 个节点都是叶节点。按图数得共 3 层,从根 1 到任意叶节点只经过 2 条边,高度为 2。
右图下方标注“退化结构:链表”。7 个节点全部偏向左侧,沿左子节点指针依次串成 1 → 2 → 3 → 4 → 5 → 6 → 7,所有节点的右子节点均为空。按图数得共 7 层,从根 1 到唯一叶节点 7 需要经过 6 条边,高度达到 6。
当每层填满成完美二叉树时,树高最小,可发挥分治优势;当节点全部偏向一侧退化为链表时,树高达到最大,按路径操作退化为线性时间。
如表 7-1 所示,在最佳结构和最差结构下,二叉树的叶节点数量、节点总数、高度等达到极大值或极小值。
表 7-1 二叉树的最佳结构与最差结构
| 完美二叉树 | 链表 | |
|---|---|---|
| 第 \(i\) 层的节点数量 | \(2^{i-1}\) | \(1\) |
| 高度为 \(h\) 的树的叶节点数量 | \(2^h\) | \(1\) |
| 高度为 \(h\) 的树的节点总数 | \(2^{h+1} - 1\) | \(h + 1\) |
| 节点总数为 \(n\) 的树的高度 | \(\log_2 (n+1) - 1\) | \(n - 1\) |