C++ 树与二叉树：核心概念、结构特征及存储实现

树的定义与核心术语

树（Tree）是一种非线性数据结构，由 n（n>=0）个有限结点组成一个具有层次关系的集合。因其视觉形态类似倒挂的树（根在上，叶在下），故得名。理解树需把握以下递归定义与约束：

1. 唯一根节点：当 n>0 时，根结点是唯一的，不存在多个根结点或无根的情况。
2. 子树互斥：除根节点外，其余结点被划分为 M（M>0）个互不相交的集合 T1, T2, ..., Tm，每个集合本身又是一棵结构类似的子树。子树之间严禁相交。

若出现子树交叉的情况，则不符合树的严格定义。以下示例展示了不符合定义的结构：

关键名词解释

为准确描述树的结构，需明确以下术语的定义：

• 节点的度：节点拥有的子树数量。例如图中 A 节点的度为 3。
• 叶节点：度为 0 的节点（终端节点）。
• 分支节点：度不为 0 的节点（非终端节点）。
• 双亲/父节点：若有子节点，则该节点为其子节点的父节点。
• 孩子/子节点：节点子树的根节点称为该节点的孩子。
• 兄弟节点：具有相同父节点的节点互为兄弟。
• 树的度：树内各节点度的最大值。
• 层次与高度：根为第 1 层，其子节点为第 2 层，以此类推；树中节点的最大层次称为树的高度（或深度）。
• 祖先与子孙：从根到某节点路径上的所有节点均为其祖先；以某节点为根的子树中任一节点均为其子孙。
• 森林：m 棵互不相交的树的集合。

树的存储结构

由于树中一个节点可能有多个孩子，简单的顺序存储（如数组）难以直接反映节点间的逻辑关系，因此通常采用链式存储。最常用的是孩子兄弟表示法（Child-Sibling Representation）。

孩子兄弟表示法实现

该方法将任意一棵树转换为二叉树：每个节点只保留两个指针，分别指向第一个孩子和下一个兄弟。这种转换使得多叉树可以用标准的二叉树结构进行存储和操作。

typedef int DataType;
struct Node
{
    struct Node* _firstChild1;    // 第一个孩子结点
    struct Node* _pNextBrother;   // 指向其下一个兄弟结点
    DataType _data;               // 结点中的数据域
};

二叉树的概念与结构

二叉树（Binary Tree）是 n（n>=0）个结点的有限集合，为空集或由一个根结点加上两棵互不相交的左子树和右子树组成。其核心特征包括：

• 最大度数为 2：每个节点最多有两棵子树，不存在度大于 2 的节点。
• 左右有序性：左子树和右子树是有顺序的，次序不能颠倒。即使只有一个子树，也必须区分是左子树还是右子树。

特殊的二叉树

满二叉树

一棵深度为 k 且含有 2^k - 1 个节点的二叉树称为满二叉树。其特征是所有分支节点都存在左子树和右子树，且所有叶子都在同一层上。

完全二叉树

对一棵二叉树按层序编号，如果编号为 i（1<=i<=n）的节点与同样深度的满二叉树中编号为 i 的节点位置完全相同，则该树为完全二叉树。满二叉树是完全二叉树的特例。

二叉树的性质与存储

二叉树的五大性质

掌握这些性质有助于分析树的结构效率：

1. 层节点数：第 i 层上至多有 2^(i-1) 个节点（i>=1）。
2. 总节点数：深度为 k 的二叉树至多有 2^k - 1 个节点。
3. 叶节点与分支节点关系：对于任何二叉树，若叶节点数为 n0，度为 2 的节点数为 n2，则 n0 = n2 + 1。
4. 完全二叉树深度：具有 n 个节点的完全二叉树深度为 ⌊log₂n⌋ + 1。

完全二叉树的数组映射（性质五）

对于含 n 个节点的完全二叉树，若从上至下、从左至右从 0 开始编号，则对任意节点 i 有：

• 若 i=0，为根节点，无双亲；若 i>0，双亲为 (i-1)/2。
• 若 2i+1 > n-1，则无左孩子；否则左孩子为 2i+1。
• 若 2i+2 > n-1，则无右孩子；否则右孩子为 2i+2。

二叉树的存储结构

顺序存储

使用数组存储二叉树。由于非完全二叉树存在大量空位会导致空间浪费，因此在实际工程中，**堆（Heap）**通常使用顺序存储（数组）。物理上是数组，逻辑上视为二叉树。

链式存储

二叉树节点通常包含一个数据域和两个指针域，称为二叉链表。这是最通用的存储方式。

typedef int BTDataType;
struct BinaryTreeNode
{
    struct BinTreeNode* _pLeft;       // 指向当前节点左孩子
    struct BinTreeNode* _pRight;      // 指向当前节点右孩子
    BTDataType _data;                 // 当前节点值域
}

以上就是 C++ 中树与二叉树的核心概念、结构性质及存储实现的详细内容，更多关于 C++ 数据结构基础与算法优化的资料请关注本站其它相关文章！