树与二叉树

树的概念

树（tree）是n（n>=0）个结点的有限集。在任意一棵非空树中：

• 有且仅有一个特定的结点称为（root）根结点
• 当n>1的时候，其余结点可以分为m（m>0）个互不相交的有限集：T₁、T₂、T₃…Tₘ。其中每一个有限集，又可以看成是一棵树，并且称之为根的子树。

---

图示：

• 根节点
  • t₁
  • t₂
  • t₃
  • t₄

---

树结点结构：
树结点包含一个数据元素以及若干个指向其子树的分支（指针）。

/* 示例代码 */  
struct TreeNode  
{  
    Element Data; // 数据域  
    struct TreeNode *t1, *t2, *t3...; // 多子树指针  
};  

struct node // 单链表结点  
{  
    int index;  
    struct node *next;  
};  

// 树结点定义  
struct TreeNode  
{  
    int data;  
    struct node *childNode_ptr; // 分支结点的集合（链表形式存储子节点下标）  
};

创建树示例

// 创建一棵树（含10个结点）  
struct tree t1[10];  

// 初始化数据  
t1[0].data = 1;  
t1[1].data = 2;  
t1[2].data = 3;  
t1[3].data = 4;  
t1[4].data = 5;  
t1[5].data = 6;  
t1[6].data = 7;  
t1[7].data = 8;  
t1[8].data = 9;  
t1[9].data = 10;  

// 建立关系：将根结点（t1[0]）的子节点下标存入链表  
t1[0].childNode_ptr = /* 链表头指针，存储子节点下标 */;

结点层次

• 定义：从根开始，根结点为第一层，根的子结点（孩子）为第二层，以此类推。
• 树的高度/深度：树中结点的最大层次。

结点的度

• 定义：结点拥有的子树数量。
  • 叶子结点（终端结点）：度为0的结点。
  • 分支结点：度不为0的结点。

---

二叉树

特点

1. 每个结点最多有两个子树（不存在度>2的结点）。
2. 子树分为左子树和右子树，次序不可颠倒。

二叉树的五大形态

1. 空二叉树
2. 只有一个根结点的二叉树
3. 只有左子树的二叉树
4. 只有右子树的二叉树
5. 左右子树均存在的二叉树（完全二叉树）

二叉树的性质

1. 第i层的最大结点数：至多 (2^{i-1}) 个结点（(i \geq 1)）。

   • 第一层：(2^{0} = 1) 个结点
   • 第二层：(2^{1} = 2) 个结点
   • 第四层：(2^{3} = 8) 个结点

2. 深度为k的二叉树最大结点数：至多 (2^{k} - 1) 个结点。

3. 叶子结点与度为2结点的关系：

   • 终端结点（叶子）数 (n_0)，度为2的结点数 (n_2)，满足 (n_0 = n_2 + 1)。

4. 满二叉树：

   • 深度为 (k) 且有 (2^{k} - 1) 个结点的二叉树（无法在不增加深度的情况下添加新结点）。

5. 完全二叉树：

   • 除最后一层外为满二叉树，最后一层结点从左至右连续排列。
   • 对完全二叉树的结点按层次编号（从1到n），编号为 (i) 的结点：
     • 左孩子（若存在）：编号 (2i)
     • 右孩子（若存在）：编号 (2i + 1)
     • 父结点：编号 (\lfloor i/2 \rfloor)（向下取整）

6. 完全二叉树的深度：

   • 具有 (n) 个结点的完全二叉树深度为 (\lfloor \log_2 n \rfloor + 1)（向下取整）。
   • 示例：(n = 11)，深度为 (\lfloor \log_2 11 \rfloor + 1 = 4)。

---

二叉树的存储结构

顺序存储结构

• 使用数组存储，下标关系：
  • 根结点：tree[0]
  • 结点 (i) 的左孩子：tree[2*i + 1]
  • 结点 (i) 的右孩子：tree[2*i + 2]

int tree[10] = {0};  
tree[0] = 1;      // 根结点  
tree[1] = 2;      // 根的左孩子（下标2*0+1）  
tree[2] = 3;      // 根的右孩子（下标2*0+2）

链式存储结构

struct node  
{  
    ElementType data;  
    struct node *lchild;  // 左子节点指针  
    struct node *rchild;  // 右子节点指针  
};

---

二叉树的遍历

访问：对结点进行打印、修改或对比操作，每个结点仅访问一次。

遍历方式

1. 先序遍历：根 → 左子树 → 右子树（根左右）
2. 中序遍历：左子树 → 根 → 右子树（左根右）
3. 后序遍历：左子树 → 右子树 → 根（左右根）
4. 层次遍历：按层从上到下、从左到右访问。

注意：遍历时需递归处理非终端结点的子树。

作业示例

给定先序和中序序列，求后序序列：

1. 先序：11 9 3 5 6 99 32 15
   中序：3 5 6 9 11 15 32 99
   后序：6 5 3 9 15 32 99 11

2. 中序：1 2 3 6 9 15 33 52
   先序：52 6 1 3 2 9 33 15
   后序：2 3 1 15 33 9 6 52

3. 中序：8 13 19 20 21 35 66
   先序：35 21 13 8 19 20 66
   后序：8 13 20 19 21 66 35

---

二叉排序树

定义

• 对任意结点：
  • 左子树所有结点值 < 该结点值
  • 右子树所有结点值 > 该结点值
• 注意：不存在值相等的结点。

结点插入

1. 空树：新结点作为根结点。
2. 非空树：
   • 若新值 < 当前结点值：
     • 左子树存在 → 递归比较左子树
     • 左子树不存在 → 新结点作为左孩子
   • 若新值 > 当前结点值：
     • 右子树存在 → 递归比较右子树
     • 右子树不存在 → 新结点作为右孩子

示例插入序列：11 → 9 → 3 → 5 → 6 → 99 → 32 → 15

1. 11 为根
2. 9 < 11 → 成为11的左孩子
3. 3 < 11 → 递归至左子树 9，3 < 9 → 成为9的左孩子
4. 5 > 3 → 成为3的右孩子
5. 6 > 5 → 成为5的右孩子

遍历特性

• 中序遍历：输出有序序列（从小到大）。

结点删除

1. 叶子结点：直接删除，父结点指针置空。
2. 只有左子树：
   • 用左子树中最大结点替换被删结点。
   • 若最大结点非左子树的根 → 调整其父结点指针指向其左孩子。
3. 只有右子树：
   • 用右子树中最小结点替换被删结点。
   • 若最小结点非右子树的根 → 调整其父结点指针指向其右孩子。
4. 左右子树均存在：
   • 可选左子树最大结点或右子树最小结点替换（操作同情况2或3）。