本章探讨了二叉树和树的基本概念、特性及应用。内容涵盖二叉树的遍历方法、树的存储结构以及两者在数据处理中的重要角色。
5.1 数的逻辑结构
### 5.1.1 树的定义与基本术语
树是一种数据结构，在这种结构中通常将数据元素称为节点。
**定义：**
- （1）有且仅有一个特定结点，称之为根。
- （2）其余所有非根节点可以被划分为m（m>0）个互不相交的有限集合T1, T2, ..., Tn。每个集合自身也是一棵树，并称为该节点的子树。
**基本术语：**
- 结点度、树的度
- 叶子结点、分支结点
- 孩子结点、兄弟结点
- 路径及其长度
- 祖先与子孙
- 层次编号及深度（高度）
- 有序树和无序树的概念
- 森林的定义
### 5.1.2 树的抽象数据类型定义
### 5.1.3 树的遍历操作
**前序遍历：**
若为空，则返回空；否则，访问根节点，并按照从左向右顺序对每一棵子树进行前序遍历。
**中序遍历：**
若为空，则返回空；否则，按从左至右顺序对各子树进行后序遍历之后再访问该层的根结点。
**层次遍历（广度优先）：**
自上而下逐层访问，在同一层级内则由左向右依次访问每个节点。
### 5.2 树的存储结构
#### 双亲表示法
树中每个元素都有唯一一个直接前驱，因此可以使用一维数组来实现，其中包含结点的数据信息和指向其双亲的信息。
#### 孩子表示法
- **多重链表：** 每个节点设置与其度数相同的指针。
- **孩子链表：** 以单向链接方式存储每个节点的孩子们，并用一个独立的头结点来标识这些孩子们组成的列表。
#### 双亲和孩子结合方法
将双亲表示法与孩子链表相结合，既保留了树结构的信息又方便访问。
#### 孩子兄弟（二叉）表示法
通过设置两个指针指向第一个孩子节点以及右兄弟的实现方式来存储树的数据结构。
### 5.3 二叉树逻辑结构
最简单的树形式之一，特别适合计算机处理。任何一般化的树都可以简单地转换为一个二叉树的形式进行表示和操作。
#### 定义与形态
- 空二叉树、只有一个根节点的二叉树等五种基本结构。
- 斜二叉树、满二叉树及完全二叉树等特殊类型定义。
#### 性质
1. 一个具有i层的完整二叉树最多有2^(i-1)个结点；
2. 深度为k的非空二叉树最少拥有k个节点，最多则可以达到(2^k - 1)个。
3. 完全二叉树中叶子的数量等于两度节点数量加一。
4. 对于完全二叉树中的任一结点i（编号从1开始），其双亲的编号为floor(i/2)，左孩子和右孩子的编号分别为2*i 和 2*i+1。
### 5.3.3 抽象数据类型定义
#### 遍历操作
- 前序遍历：先访问根结点，然后按顺序遍历其左右子树。
- 中序遍历：依次对左子树进行中序遍历，再访问当前节点最后对其右子树做同样的处理。
- 后续遍历：首先递归地对每个孩子执行后序操作，之后才轮到根结点本身。
### 5.4 存储结构及实现
#### 顺序存储
将二叉树按照完全二叉树的规则编号，并按此顺序保存节点信息至一维数组中。
#### 链式存储
每个元素包括数据域和指向其左右孩子的指针。
- **三叉链表**：增加一个指向双亲结点的指针，便于回溯。
- 线索化二叉树通过添加前驱与后继指针来优化遍历操作。
### 5.5 遍历算法
#### 前序、中序和后续非递归实现
使用栈结构模拟递归过程。关键在于正确地调整结点访问顺序以及何时保存或弹出当前节点信息到输出序列中去。
### 5.6 树与二叉树的转换
- **树转为二叉树**：通过添加和删除连线
5星
