树和二叉树

树和二叉树

• 树的定义和基本术语
• 二叉树的定义
• 二叉树的性质
• 线索二叉树
• 森林与二叉树的转换
• 哈夫曼树的基本概念
  • 构造哈夫曼树口诀

树的定义和基本术语

树（Tree） 是 n (n >= 0)个结点的有限集。

在任意一颗非空树中：

​ 1. 有且仅有一个 根（root） 结点

​ 2. 当 n > 1 时，其余结点可分为 m（m > 0）个互不相交的有限集T1、T2，… ，Tm，其中每一个集合本身又是一颗树，并且称为根的 子树（SubTree）。

树的 结点 包含一个数据元素及或干个指向子树的分支。

根结点：非空树中无前驱结点的结点。

结点的度：结点拥有的子树数。

度为 0 的结点称为 叶子（Leaf）或 终端结点。

结点的子树的根称为该结点的 孩子，该结点称为孩子的 双亲。

树的度：树内各结点的度的最大值。

树的深度：树中结点的最大层次。

树的基本概念和术语

有序树：树中结点的各子树从左至右有次序（最左边的为第一个孩子）。

无序树：树中结点的各子树无次序。

森林：是 m（m >= 0）棵互不相交的树的集合。

• 把根结点删除，树就变成了森林。
• 一棵树可以看成是一个特殊的森林。
• 给森林中的各子树加上一个双亲结点，森林就变成了树。

树 一定是 森林

森林 不一定是 树

二叉树的定义

二叉树（Binary Tree）是 n (n >= 0)个结点的有限集，它或者是空集 (n= 0),或者由一个根结点 及 两棵互不相交 的分别称作这个根的 左子树 和 右子树 的二叉树组成。

特点：

1. 每个结点最多有俩孩子（二叉树中不存在度大于 2 的结点）。
2. 子树有左右之分，其次序不能颠倒。
3. 二叉树可以是空集合，根可以有空的左子树或空的右子树。

注：虽然二叉树与树概念不同，但有关树的基本术语对二叉树都适用。

二叉树的性质

完全二叉树：深度为k的具有n个结点的二叉树，当且仅当其每一个结点都与深度为k的 满二叉树中编号 为1 ~ n的结点一一对应时， 称之为完全二叉树。

满二叉树 一定是 完全二叉树

完全二叉树 不一定是 满二叉树

注：在满二叉树中，从最后一个结点开始，连续 去掉 任意 个结点，即是一棵完全二叉树。（一定是连续的去掉！！！）

性质4： 具有 n 个结点的完全二叉树的深度为

性质5：如果对一棵有 n 个结点的 完全二叉树（深度为

的结点按层序编号（从第1层到第

层，每层从左到右），则对任一结点 i（1 <= i <= n）,有:

1. 如果 i = 1，则结点 i 是二叉树的根，无双亲；如果 i >1，则其 双亲是结点

。

1. 如果 2i > n，则结点 i 为叶子结点，无左孩子；否则，其 左孩子是结点 2i。
2. 如果 2i + 1 > n，则结点 i 无右孩子；否则，其右孩子是结点 2i + 1。

性质4：表明了完全二叉树 结点数n 与完全二叉树 深度k 之间的关系 。

性质5：表明了完全二叉树中 双亲结点编号 与 孩子结点编号 之间的关系。

线索二叉树

利用二叉链表中的空指针域:

• 如果某个结点的 左孩子为空，则将空的左孩子指针域改为 指向其前驱
• 如果某结点的 右孩子为空，则将空的右孩子指针域改为 指向其后继
• 这种改变指向的指针称为 "线索”
• 加上了线索的二叉树称为 线索二叉树(Threaded Binary Tree)
• 对二叉树按某种遍历次序使其变为线索二叉树的过程叫 线索化

森林与二叉树的转换

树变二叉树：兄弟相连留长子

二叉树变树：左孩右右连双亲，去掉原来右孩线

森林变二叉树：树变二叉跟相连

二叉树变森林：去掉全部右孩线，孤立二叉再还原

哈夫曼树的基本概念

路径：从树中一个结点到另一个结点之间的分支构成这两个结点间的路径。

结点的路径长度：两个结点间路径上的 分支数。

树的路径长度：从 树根 到每个结点的 路径长度之和。记住：TL

结点数目相同的二叉树中，完全二叉树是路径长度最短的二叉树。

权(weight)：将树中结点赋给一个有着某种含义的数值，则这个数值称为该 结点的权。

结点的带权路径长度：从 根结点 到该结点之间的 路径长度 与该结点的 权 的 乘积。

树的带权路径长度：树中所有 叶子 结点的 带权路径长度之和。

哈夫曼树：最优树（带权路径长度（WPL）最短的树）。

“带权路径长度最短”是在“度相同” 的树中比较而得的结果，因此有最优二叉树、最优三叉树之称等等

哈夫曼树：最优二叉树（带权路径长度（WPL）最短的二叉树）。

构造哈夫曼树口诀

​ 1. 构造森林全是根

​ 2. 选用两小造新树

​ 3. 删除两小添新人

​ 4. 重复 2、3 剩单根

包含 n 棵树的森林要经过 n - 1次合并才能形成哈夫曼树，共产生 n - 1 个新结点。

包含 n 个叶子结点的哈夫曼树中共有 2n - 1 个结点。

哈夫曼树的结点的度为 0 或 2，没有度为 1 的结点。