目录

• 4.1 树的基本概念
  • 4.1.1 树的定义
  • 4.1.2 基本术语
  • 4.1.3 树的性质
• 4.2 二叉树的概念
  • 4.2.1 二叉树的定义及其主要特性
    • （1）二叉树的定义
    • （2）几个特殊的二叉树
    • （3）二叉树的性质
  • 4.2.2 二叉树的存储结构
    • （1）顺序存储结构
    • （2）链式存储结构
• 4.3 二叉树的遍历和线索二叉树
  • 4.3.1 二叉树的遍历
    • （1）先序遍历（PreOrder）
    • （2）中序遍历（InOrder）
    • （3）后序遍历（PostOrder）
    • （4）递归算法和非递归算法的转换
    • （5）层次遍历
    • （6）由遍历序列构造二叉树
  • 4.3.2 线索二叉树
    • （1）线索二叉树的基本概念
    • （2）线索二叉树的构造
    • （3）线索二叉树的遍历
• 4.4 树、森 林
  • 4.4.1 树的存储结构
  • 4.4.2 树、森林与二叉树的转换
  • 4.4.3 树和森林的遍历
  • 4.4.4 树的应用—并查集
• 4.5 树与二叉树的应用
  • 4.5.1 二叉排序树
    • （1）二叉排序树的定义
    • （2）二叉排序树的查找
    • （3）二叉排序树的插入
    • （4）二叉排序树的构造
    • （5）二叉排序树的删除
    • （6）二叉排序树的査找效率分析
  • 4.5.2 平衡二叉树（Balanced Binary Tree）
    • （1）平衡二又树的定义
    • （2）平衡二叉树的插入
    • （3）平衡二叉树的查找
  • 4.5.3 哈夫曼（Huffman）树和哈夫曼编码
    • （1）哈夫曼树的定义
    • （2）哈夫曼树的构造
    • （3）哈夫曼编码

4.1 树的基本概念

4.1.1 树的定义

树是 N（\(N\ge 0\)）个结点的有限集合，N=0 时，称为空树，这是一种特殊情况。
在任意一棵非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当 N>1 时，其余结点可分为 m（m>0）个互不相交的有限集合 \(T_1,T_2,\cdots,T_m\)，其中每一个集合本身又是一棵树，并且称为根结点的子树。

显然树的定义是递归的，是一种递归的数据结构。
树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。
2. 树中所有结点可以有零个或多个后继结点。

树适合于表示具有层次结构的数据。
树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在 n 个结点的树中有 n-1 条边。
而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

4.1.2 基本术语

下面结合图 4-1 中的树来说明一些基本术语和概念。

1. 考虑结点 K。
   根 A 到结点 K 的唯一路径上的任意结点，称为结点 K 的祖先结点。
   如结点 B 是结点 K 的祖先结点，而结点 K 是结点 B 的子孙结点。
   路径上最接近结点 K 的结点 E 称为 K 的双亲结点，而 K 为结点 E 的孩子结点。
   根 A 是树中唯一没有双亲的结点。
   有相同双亲的结点称为兄弟结点，如结点 K 和结点 L 有相同的双亲结点 E，即 K 和 L 为兄弟结点。
2. 树中一个结点的子结点个数称为该结点的度，树中结点的最大度数称为树的度。
   如结点 B 的度为 2,结点 D 的度为 3,树的度为 3。
3. 度大于 0 的结点称为分支结点（又称非终端结点）；
   度为 0（没有子女结点）的结点称为叶子结点（又称终端结点）。
4. 结点的深度、高度和层次。
   结点的层次从树根开始定义，根结点为第 1 层（有些教材中将根结点定义为第 0 层），它的子结点为第 2 层，依此类推。
   结点的深度是从根结点开始自顶向下逐层累加的。
   结点的高度是从叶结点开始自底向上遂层累加的。
   树的高度（又称深度）是树中结点的最大层数。
   图 4-1 中树的高度为 4。
5. 有序树和无序树：
   树中结点的子树从左到右是有次序的，不能交换，这样的树叫做有序树，
   有序树中，一个结点其子结点按从左到右顺序出现是有关联的。
   反之则称为无序树。在图 4-1中，若将子结点位置互换，则变成一棵不同的树。

6. 路径和路径长度：树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。
   在图 4-1 中，结点 A 和结点 K 的路径长度为 3，中间经过结点 B 和结点 E。

   注意：
   由于树中的分支是有向的，即从双亲结点指向孩子结点，所以树中的路径是从上向下的，同一双亲结点的两个孩子结点之间不存在路径。

7. 森林：森林是 m（\(m\ge O\)）棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。
   反之，只要给 n 棵独立的树加上一个结点，并把这 n 棵树作为该结点的子树，则森林就变成了树。

   注意：
   上述板念无需刻意记忆，根据实例理解即可。
   考研不大可能直接考查概念，都是结合具体的题目考查。
   做題时，遇到不熟悉的概念可以再翻书，练习得多自然就记住了。

4.1.3 树的性质

（编辑：ASP站长网）