二叉树简介

二叉树概述

本模块介绍计算机科学中最基础的结构之一：二叉树。这里的“树”一词源于其图形表示形式——当我们绘制它们时，结果往往类似于森林中的树木。二叉树有多种定义方式。从数学角度讲，二叉树是一个连通、无向、有限且无环的图，且任意顶点的度数不超过三。

在大多数计算机科学应用中，二叉树是带根的：一个度数最多为二的特殊节点 r 被称为根。对于每个节点 $u \neq r$，从 u 到根 r 的路径上的第二个节点称为 u 的父节点。与 u 相邻的其他节点则称为 u 的子节点。我们通常关注的是有序二叉树，因此会区分 u 的左子节点和右子节点。

二叉树的结构

在图示中，二叉树通常从根节点向下绘制，根位于图的顶部，左子节点和右子节点分别位于其下方的左侧和右侧位置。

例如，下图展示了一棵包含九个节点的二叉树。

由于二叉树的重要性，人们发展出一套专门的术语：

• 二叉树中节点 u 的深度是指从 u 到根节点的路径长度。
• 如果节点 w 位于从 u 到根 r 的路径上，则称 w 是 u 的祖先，而 u 是 w 的后代。
• 节点 u 的子树是以 u 为根，包含 u 所有后代的二叉树。
• 节点 u 的高度是从 u 到其某个后代的最长路径长度。
• 一棵树的高度即为其根节点的高度。
• 若一个节点没有子节点，则称其为叶子节点。

有时我们会将树扩展为包含外部节点的形式。任何没有左子节点的节点，其左子节点都设为一个外部节点；同理，任何没有右子节点的节点，其右子节点也设为一个外部节点（见下图）。通过归纳法可以很容易验证：一棵包含 $n \ge 1$ 个实际节点的二叉树，恰好有 $n + 1$ 个外部节点。