树的表示方法

常用术语：

• 根节点(root node)
• 叶节点(leaf node)，或者终端节点 :没有子节点的节点
• 边(edge):链接两个节点的线段
• 节点所在的层(level)：从顶至底递增，根节点所在的层为1
• 节点的度(degree):节点的子节点的数量
• 树的度：树中各节点度的最大值
• 二叉树的高度(height):s从根节点到最远节点所经过的边的数量
• 节点的深度(depth):从根节点到该节点所经过的边的数量
• 节点的高度(height):从距离该节点最远的叶节点到该节点所经过的边的数量
• 兄弟(sibling):同一双亲节点互为兄弟
• 有序树:任一节点的各子树，若从左至右是有次序的，则称为有序树

二叉树

二叉树性质集

性质5.1（层结点上限）

在二叉树的第$i$层上至多有$2^{i-1}$个结点（$i \geq 1$）

性质5.2（树结点上限）

深度为$k$的二叉树最多有$2^{k} - 1$个结点

性质5.3（叶子结点关系）

在非空二叉树中，设：

• $n_0$：叶子结点数
• $n_2$：度为2的结点数

则满足关系：
$n_0 = n_2 + 1$

性质5.4（完全二叉树深度）

对含$n$个结点的完全二叉树，其深度$k$满足：
$k = \lfloor \log_2 n \rfloor + 1$

性质5.5（结点关系判定）

对层序编号（从1开始）的完全二叉树，结点$i$（$1 \leq i \leq n$）满足：

1. ​​双亲结点​​： $$\text{parent}(i) = \begin{cases} \text{不存在} & i = 1 \\ \lfloor i/2 \rfloor & i \geq 2 \end{cases}$$
2. ​​左孩子结点​​： $$\text{leftChild}(i) = \begin{cases} \text{不存在} & 2i > n \\ 2i & 2i \leq n \end{cases}$$
3. ​​右孩子结点​​： $$\text{rightChild}(i) = \begin{cases} \text{不存在} & 2i+1 > n \\ 2i+1 & 2i+1 \leq n \end{cases}$$

​​结构特性​​：

• 当$i > \lfloor n/2 \rfloor$时，结点$i$必为叶子结点
• 完全二叉树的空指针域数恒等于$n+1$（可通过性质5.3推导）

==二叉树==

struct TreeNode{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode(int x): val(x), left(nullptr),right(nullptr){}
};

==数组表示==

struct ATreeNode{

    /*

        数组表示的二叉树

        某节点的索引为i，则左子节点的索引为2i+1，右子节点的索引为2i+2

        如果没有相应节点，需要用None表示

        适合表示完美二叉树

    */
    int size;
    int * trees;
};

==静态链表==

struct bnode2{
	int data;
	int lchild,rchild;
} t[n+1];

==线索二叉树==

1. 空指针利用
   普通二叉树的每个节点有左右两个指针域，但非叶子节点中存在大量空指针（n个节点的二叉树有n+1个空指针）。线索二叉树通过将这些空指针改为指向遍历序列中的前驱或后继节点，形成线索链。

2. 线索与标志位
   • 线索：指向遍历序列中前驱或后继节点的指针称为线索。 • 标志位：每个节点新增ltag和rtag两个标志位，用于区分指针指向的是子节点还是线索： ◦ ltag=0：左指针指向左孩子；ltag=1：左指针指向前驱节点。 ◦ rtag=0：右指针指向右孩子；rtag=1：右指针指向后继节点。

3. 线索化过程
   在遍历二叉树时，动态修改空指针并设置标志位。例如中序线索化时，递归处理左子树，修改当前节点的前驱线索（若左子树为空），并更新前驱节点的后继线索（若前驱节点的右子树为空）。

树的算法部分