前言「树」在编程里既是一个数据结构概念也是一堆细分名词的集合根、叶、度、深度、高度、满二叉树、完全二叉树、二叉搜索树、平衡树、堆……这些词在不同教材里的定义并不完全一致尤其是「满二叉树」中文语境和英文语境指的不是同一件事。最常见的混淆有两个。第一把「满二叉树」和「完全二叉树」当成同义词。中文教材里的「满二叉树」通常指每一层都填满的完美二叉树perfect binary tree而英文的 full binary tree 指「每个节点有 0 个或 2 个孩子」两者不是一回事。第二把「深度」和「高度」混用或者不说明根节点的深度是 0 还是 1导致同一个公式在不同资料里差一。本文按「基本术语 → 二叉树分类 → 特殊二叉树 → 存储表示 → 遍历 → C 定义」的顺序梳理重点澄清容易混淆的定义最后给出一个可用的节点类型和几个基本操作。一、树的基本术语与二叉树分类树tree是 n 个节点的有限集合满足有且仅有一个根节点root。除根外每个节点有且仅有一个父节点parent。任意节点都可以通过父链追溯到根不存在环。由此可推出n 个节点的树恰有 n−1 条边。常用术语术语含义根root没有父节点的唯一节点叶leaf没有子节点的节点内部节点至少有一个子节点的节点度degree一个节点的子节点个数树的度所有节点度的最大值兄弟sibling同一个父节点的其他子节点祖先 / 后代沿父链 / 子链可达的节点层次level根为第 1 层子节点依次加 1深度depth从根到该节点的边数根为 0高度height从该节点到最远叶子的边数叶子为 0森林forest若干棵互不相交的树关于深度与高度本文统一采用「边数」口径根的深度为 0叶子高度为 0树的高度等于根的高度。也有教材用「节点数」口径根深度为 1叶子高度为 1两种都能自洽但同一个公式里不能混用。例如「高度为 h 的二叉树最多有 2^h − 1 个节点」成立的前提是 h 以节点数计若按边数计则最多是 2^(h1) − 1 个。二叉树binary tree是每个节点至多有两个子节点、且左右子树有顺序之分的树。「有序」很关键只有左孩子和只有右孩子是两种不同的结构不能互换。1.1 满二叉树、完全二叉树、完美二叉树这三个词最容易混。完美二叉树perfect binary tree所有内部节点都有两个子节点且所有叶子在同一层。节点总数恰好是 2^h − 1h 为层数。完全二叉树complete binary tree除最后一层外每层都填满最后一层的节点从左到右连续排列中间没有空洞。完美二叉树一定是完全二叉树反之不成立。满二叉树这个中文词有歧义。中文教材如国内数据结构课程通常把它定义为「每一层都填满」即完美二叉树。英文 full binary tree 的定义是「每个节点有 0 个或 2 个子节点」允许叶子分布在不同层。本文在需要精确表达时直接写「完美二叉树」或「每个节点 0 或 2 个孩子」避免使用有歧义的「满二叉树」。三者的关系可以这样记完美二叉树 ⊂ 完全二叉树完美二叉树 ⊂ 每个节点 0 或 2 个孩子英文 full完全二叉树 与 英文 full 没有包含关系一棵只有左孩子的链是 neither一棵所有内部节点都有两个孩子但叶子不同层的树是英文 full 但不是完全二叉树。1.2 二叉树的性质对任意非空二叉树设度为 0、1、2 的节点数分别为 n0、n1、n2节点总数 n n0 n1 n2。边数 n − 1 n1 2·n2每个度为 1 的节点贡献 1 条向下的边度为 2 的贡献 2 条。联立得n0 n2 1即叶子数总比双孩子节点数多 1。另外第 i 层最多有 2^(i−1) 个节点层数从 1 计。深度为 h 的二叉树最多有 2^h − 1 个节点深度从 1 计。n 个节点的完全二叉树高度为 ⌊log₂ n⌋ 1层数口径。这些性质在推导堆、线段树的复杂度时经常用到。二、特殊二叉树2.1 二叉搜索树二叉搜索树binary search tree, BST满足对任意节点左子树所有值小于它右子树所有值大于它。中序遍历得到严格递增序列。BST 的查找、插入、删除平均 O(log n)但最坏情况退化成链是 O(n)。是否平衡决定实际性能标准库的std::map/std::set通常用红黑树保证 O(log n)。2.2 平衡二叉树平衡二叉树指左右子树高度差有界的 BST。AVL 树要求任意节点左右子树高度差不超过 1通过旋转维持红黑树用颜色约束近似平衡插入删除的旋转次数更少。两者都保证树高 O(log n)。「平衡」不是单一标准不同结构有不同定义讨论时要说明是哪种平衡条件。2.3 堆堆heap是一棵完全二叉树满足堆序大根堆中每个节点不小于其子节点小根堆反之。因为是完全二叉树可以用数组紧凑存储不需要指针。std::priority_queue默认是大根堆底层用std::vector加堆算法实现。2.4 Trie、B 树等Trie前缀树按字符分层用于字符串检索B 树、B 树是多路平衡树用于磁盘索引。它们的「树」定义更宽泛节点可以有多个孩子不属于二叉树。三、存储表示3.1 链式存储每个节点保存值和若干子节点指针。二叉树最自然// 适用于 C17struct TreeNode {int val;TreeNode* left;TreeNode* right;explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}};优点是指针直接、插入删除方便缺点是每个节点一次分配缓存局部性差。3.2 顺序存储用数组存完全二叉树下标i的节点左孩子在2i1右孩子在2i2父节点在(i-1)/2根下标为 0。// 适用于 C17std::vectorint heap{10, 7, 9, 3, 5};// heap[0] 的左孩子是 heap[1]右孩子是 heap[2]这种表示只适合完全二叉树。普通二叉树用数组会浪费大量空间退化成链时尤其严重。3.3 孩子兄弟表示法多叉树可以用「左孩子、右兄弟」两个指针表示把任意树转成二叉树。这是「森林与二叉树相互转换」的基础。四、遍历与 C 定义示例遍历顺序典型用途前序preorder根 → 左 → 右复制树、序列化中序inorder左 → 根 → 右BST 有序输出后序postorder左 → 右 → 根释放节点、计算子树聚合层序level order按层从左到右求宽度、最短路径前序 中序、或后序 中序可以唯一确定一棵二叉树前序 后序不能无法区分只有一个孩子时的左右。4.1 C 定义示例用std::unique_ptr表达独占所有权避免手动delete// 适用于 C17#include algorithm#include iostream#include memory#include utilitystruct TreeNode {int val;std::unique_ptrTreeNode left;std::unique_ptrTreeNode right;explicit TreeNode(int v) : val(v) {}};int height(const TreeNode* node) {if (node nullptr) return 0;return 1 std::max(height(node-left.get()), height(node-right.get()));}int countNodes(const TreeNode* node) {if (node nullptr) return 0;return 1 countNodes(node-left.get()) countNodes(node-right.get());}void inorder(const TreeNode* node) {if (node nullptr) return;inorder(node-left.get());std::cout node-val ;inorder(node-right.get());}int main() {auto root std::make_uniqueTreeNode(4);root-left std::make_uniqueTreeNode(2);root-right std::make_uniqueTreeNode(6);root-left-left std::make_uniqueTreeNode(1);root-left-right std::make_uniqueTreeNode(3);std::cout height height(root.get()) \n; // 3std::cout count countNodes(root.get()) \n; // 5std::cout inorder: ;inorder(root.get()); // 1 2 3 4 6std::cout \n;return 0;}几点说明这里的高度采用「节点数」口径空树高度 0叶子高度 1所以这棵树高度为 3。前文术语表用的是「边数」口径两者差一写代码时要统一。本文代码统一用节点数便于递归。unique_ptr的析构是递归的根销毁时依次销毁左右子树。树非常深时可能导致栈溢出极端场景需要显式后序释放。inorder接收裸指针不涉及所有权只做观察。常见坑点❌ 把「满二叉树」和「完全二叉树」混用text 认为所有满二叉树都满足数组下标 2i1 的规律 ✅ 只有完全二叉树适合顺序存储完美二叉树是它的特例。❌ 深度与高度口径混用cpp // 术语按边数代码按节点数公式差一 ✅ 在文档里明确口径代码与公式保持一致。❌ 认为「每个节点 0 或 2 个孩子」就是完全二叉树。✅ 这是英文 full 的定义完全二叉树要求最后一层从左到右连续。❌ 用数组存非完全二叉树。✅ 普通二叉树用链式存储数组只用于完全二叉树堆、线段树。❌ 释放树时只delete根节点。✅ 递归释放子节点或用unique_ptr自动递归析构。❌ 认为前序 后序能唯一确定二叉树。✅ 需要中序参与前序 后序在单孩子情况下有二义。❌ 递归求高度时对空树返回 1。✅ 空树高度按定义为 0叶子为 1节点数口径。❌ 在 BST 中插入重复值时随意放左或放右。✅ 明确重复策略拒绝、计数、统一放一侧并保持中序性质。总结概念关键点树n 个节点、n−1 条边、无环连通深度 / 高度明确用边数还是节点数完美二叉树每层填满节点数 2^h−1完全二叉树最后一层从左到右连续可数组存储英文 full每个节点 0 或 2 个孩子BST中序有序性能取决于平衡堆完全二叉树 堆序树的定义不难难在术语的精确性。写文档或交流时把「深度按边数计」「满二叉树指完美二叉树」这类约定先讲清楚能避免大量无谓的争执。写代码时所有权用unique_ptr表达遍历用递归或显式栈基本就不会出错。 
长河君 · 2026/11/6 2:07:44 · 阅读 1.2k C++关于树的定义全面梳理
前言「树」在编程里既是一个数据结构概念也是一堆细分名词的集合根、叶、度、深度、高度、满二叉树、完全二叉树、二叉搜索树、平衡树、堆……这些词在不同教材里的定义并不完全一致尤其是「满二叉树」中文语境和英文语境指的不是同一件事。最常见的混淆有两个。第一把「满二叉树」和「完全二叉树」当成同义词。中文教材里的「满二叉树」通常指每一层都填满的完美二叉树perfect binary tree而英文的 full binary tree 指「每个节点有 0 个或 2 个孩子」两者不是一回事。第二把「深度」和「高度」混用或者不说明根节点的深度是 0 还是 1导致同一个公式在不同资料里差一。本文按「基本术语 → 二叉树分类 → 特殊二叉树 → 存储表示 → 遍历 → C 定义」的顺序梳理重点澄清容易混淆的定义最后给出一个可用的节点类型和几个基本操作。一、树的基本术语与二叉树分类树tree是 n 个节点的有限集合满足有且仅有一个根节点root。除根外每个节点有且仅有一个父节点parent。任意节点都可以通过父链追溯到根不存在环。由此可推出n 个节点的树恰有 n−1 条边。常用术语术语含义根root没有父节点的唯一节点叶leaf没有子节点的节点内部节点至少有一个子节点的节点度degree一个节点的子节点个数树的度所有节点度的最大值兄弟sibling同一个父节点的其他子节点祖先 / 后代沿父链 / 子链可达的节点层次level根为第 1 层子节点依次加 1深度depth从根到该节点的边数根为 0高度height从该节点到最远叶子的边数叶子为 0森林forest若干棵互不相交的树关于深度与高度本文统一采用「边数」口径根的深度为 0叶子高度为 0树的高度等于根的高度。也有教材用「节点数」口径根深度为 1叶子高度为 1两种都能自洽但同一个公式里不能混用。例如「高度为 h 的二叉树最多有 2^h − 1 个节点」成立的前提是 h 以节点数计若按边数计则最多是 2^(h1) − 1 个。二叉树binary tree是每个节点至多有两个子节点、且左右子树有顺序之分的树。「有序」很关键只有左孩子和只有右孩子是两种不同的结构不能互换。1.1 满二叉树、完全二叉树、完美二叉树这三个词最容易混。完美二叉树perfect binary tree所有内部节点都有两个子节点且所有叶子在同一层。节点总数恰好是 2^h − 1h 为层数。完全二叉树complete binary tree除最后一层外每层都填满最后一层的节点从左到右连续排列中间没有空洞。完美二叉树一定是完全二叉树反之不成立。满二叉树这个中文词有歧义。中文教材如国内数据结构课程通常把它定义为「每一层都填满」即完美二叉树。英文 full binary tree 的定义是「每个节点有 0 个或 2 个子节点」允许叶子分布在不同层。本文在需要精确表达时直接写「完美二叉树」或「每个节点 0 或 2 个孩子」避免使用有歧义的「满二叉树」。三者的关系可以这样记完美二叉树 ⊂ 完全二叉树完美二叉树 ⊂ 每个节点 0 或 2 个孩子英文 full完全二叉树 与 英文 full 没有包含关系一棵只有左孩子的链是 neither一棵所有内部节点都有两个孩子但叶子不同层的树是英文 full 但不是完全二叉树。1.2 二叉树的性质对任意非空二叉树设度为 0、1、2 的节点数分别为 n0、n1、n2节点总数 n n0 n1 n2。边数 n − 1 n1 2·n2每个度为 1 的节点贡献 1 条向下的边度为 2 的贡献 2 条。联立得n0 n2 1即叶子数总比双孩子节点数多 1。另外第 i 层最多有 2^(i−1) 个节点层数从 1 计。深度为 h 的二叉树最多有 2^h − 1 个节点深度从 1 计。n 个节点的完全二叉树高度为 ⌊log₂ n⌋ 1层数口径。这些性质在推导堆、线段树的复杂度时经常用到。二、特殊二叉树2.1 二叉搜索树二叉搜索树binary search tree, BST满足对任意节点左子树所有值小于它右子树所有值大于它。中序遍历得到严格递增序列。BST 的查找、插入、删除平均 O(log n)但最坏情况退化成链是 O(n)。是否平衡决定实际性能标准库的std::map/std::set通常用红黑树保证 O(log n)。2.2 平衡二叉树平衡二叉树指左右子树高度差有界的 BST。AVL 树要求任意节点左右子树高度差不超过 1通过旋转维持红黑树用颜色约束近似平衡插入删除的旋转次数更少。两者都保证树高 O(log n)。「平衡」不是单一标准不同结构有不同定义讨论时要说明是哪种平衡条件。2.3 堆堆heap是一棵完全二叉树满足堆序大根堆中每个节点不小于其子节点小根堆反之。因为是完全二叉树可以用数组紧凑存储不需要指针。std::priority_queue默认是大根堆底层用std::vector加堆算法实现。2.4 Trie、B 树等Trie前缀树按字符分层用于字符串检索B 树、B 树是多路平衡树用于磁盘索引。它们的「树」定义更宽泛节点可以有多个孩子不属于二叉树。三、存储表示3.1 链式存储每个节点保存值和若干子节点指针。二叉树最自然// 适用于 C17struct TreeNode {int val;TreeNode* left;TreeNode* right;explicit TreeNode(int v) : val(v), left(nullptr), right(nullptr) {}};优点是指针直接、插入删除方便缺点是每个节点一次分配缓存局部性差。3.2 顺序存储用数组存完全二叉树下标i的节点左孩子在2i1右孩子在2i2父节点在(i-1)/2根下标为 0。// 适用于 C17std::vectorint heap{10, 7, 9, 3, 5};// heap[0] 的左孩子是 heap[1]右孩子是 heap[2]这种表示只适合完全二叉树。普通二叉树用数组会浪费大量空间退化成链时尤其严重。3.3 孩子兄弟表示法多叉树可以用「左孩子、右兄弟」两个指针表示把任意树转成二叉树。这是「森林与二叉树相互转换」的基础。四、遍历与 C 定义示例遍历顺序典型用途前序preorder根 → 左 → 右复制树、序列化中序inorder左 → 根 → 右BST 有序输出后序postorder左 → 右 → 根释放节点、计算子树聚合层序level order按层从左到右求宽度、最短路径前序 中序、或后序 中序可以唯一确定一棵二叉树前序 后序不能无法区分只有一个孩子时的左右。4.1 C 定义示例用std::unique_ptr表达独占所有权避免手动delete// 适用于 C17#include algorithm#include iostream#include memory#include utilitystruct TreeNode {int val;std::unique_ptrTreeNode left;std::unique_ptrTreeNode right;explicit TreeNode(int v) : val(v) {}};int height(const TreeNode* node) {if (node nullptr) return 0;return 1 std::max(height(node-left.get()), height(node-right.get()));}int countNodes(const TreeNode* node) {if (node nullptr) return 0;return 1 countNodes(node-left.get()) countNodes(node-right.get());}void inorder(const TreeNode* node) {if (node nullptr) return;inorder(node-left.get());std::cout node-val ;inorder(node-right.get());}int main() {auto root std::make_uniqueTreeNode(4);root-left std::make_uniqueTreeNode(2);root-right std::make_uniqueTreeNode(6);root-left-left std::make_uniqueTreeNode(1);root-left-right std::make_uniqueTreeNode(3);std::cout height height(root.get()) \n; // 3std::cout count countNodes(root.get()) \n; // 5std::cout inorder: ;inorder(root.get()); // 1 2 3 4 6std::cout \n;return 0;}几点说明这里的高度采用「节点数」口径空树高度 0叶子高度 1所以这棵树高度为 3。前文术语表用的是「边数」口径两者差一写代码时要统一。本文代码统一用节点数便于递归。unique_ptr的析构是递归的根销毁时依次销毁左右子树。树非常深时可能导致栈溢出极端场景需要显式后序释放。inorder接收裸指针不涉及所有权只做观察。常见坑点❌ 把「满二叉树」和「完全二叉树」混用text 认为所有满二叉树都满足数组下标 2i1 的规律 ✅ 只有完全二叉树适合顺序存储完美二叉树是它的特例。❌ 深度与高度口径混用cpp // 术语按边数代码按节点数公式差一 ✅ 在文档里明确口径代码与公式保持一致。❌ 认为「每个节点 0 或 2 个孩子」就是完全二叉树。✅ 这是英文 full 的定义完全二叉树要求最后一层从左到右连续。❌ 用数组存非完全二叉树。✅ 普通二叉树用链式存储数组只用于完全二叉树堆、线段树。❌ 释放树时只delete根节点。✅ 递归释放子节点或用unique_ptr自动递归析构。❌ 认为前序 后序能唯一确定二叉树。✅ 需要中序参与前序 后序在单孩子情况下有二义。❌ 递归求高度时对空树返回 1。✅ 空树高度按定义为 0叶子为 1节点数口径。❌ 在 BST 中插入重复值时随意放左或放右。✅ 明确重复策略拒绝、计数、统一放一侧并保持中序性质。总结概念关键点树n 个节点、n−1 条边、无环连通深度 / 高度明确用边数还是节点数完美二叉树每层填满节点数 2^h−1完全二叉树最后一层从左到右连续可数组存储英文 full每个节点 0 或 2 个孩子BST中序有序性能取决于平衡堆完全二叉树 堆序树的定义不难难在术语的精确性。写文档或交流时把「深度按边数计」「满二叉树指完美二叉树」这类约定先讲清楚能避免大量无谓的争执。写代码时所有权用unique_ptr表达遍历用递归或显式栈基本就不会出错。