树的定义

• 树是n个结点的有限集。n=0时称为空树。在任意一棵非空树中：
  1. 有且仅有一个特定的称为根的结点
  2. 当n>1时，其余结点可分为m个(m>0)个互不相交的有限集T1、T2、...、Tm
  3. 每一个集合本身又是一棵树，并且称为根的子树

结点分类

• 结点拥有的子树数称为结点的度
• 度为0的结点称为叶结点或终端结点
• 度不为0的结点称为非终端结点或分支结点
• 除根结点之外，分支结点也称内部结点
• 树的度是树内各结点度的最大值

结点之间的关系

• 结点的子树的根称为该结点的孩子，相应的，该结点称为孩子的双亲
• 同一个双亲的孩子之间互称兄弟
• 结点的祖先是从该结点所经的分支上的所有结点
• 以某结点为根的子树中的任一结点都称为该结点的子孙

树的其他概念

• 结点的层次从根开始定义起，根为第一层，根的孩子为第二层
• 其双亲在同一层结点互为堂兄弟
• 树中结点的最大层次称为树的深度
• 树中结点的各子树看成是从左到右是有次序的，不能互换的，则称该树为有序树，否则无序树
• 森林是m棵互不相交的树的集合

树的存储结构

双亲表示

• 附设一个指示器指示其双亲结点到链表中的位置

孩子表示法

• 每一个结点有多个指针域，其中每一个指针指向一棵子树的根结点，我们把这种办法称为多重链表表示法
• 把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，放进一个一维数组中

孩子兄弟表示法

• 任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟

二叉树的定义

• 二叉树是n个结点的有限集合，该集合或者为空集，或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树构成

特点

1. 每棵结点最多有两棵子树
2. 左子树和右子树是有顺序的，次序不能颠倒
3. 即使树中只有一棵子树，也要区分是左子树还是右子树

特殊二叉树

1. 斜树
   • 所有结点都只有左子树的二叉树称为左斜树，所有结点都是只有右子树的二叉树叫右斜树，这两者统称为斜树
2. 满二叉树
   • 在一棵二叉树上，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树
3. 完全二叉树
   • 对一棵具有n个结点的二叉树按层序编号，如果编号为i的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树
   • 满二叉树一定是一棵完全二叉树，完全二叉树不一定是满的
   • 特点：
     1. 叶子结点只能出现在最下两层
     2. 最下层的叶子一定集中在左部连续位置
     3. 倒数两层，若有叶子结点，一定都在右部连续位置
     4. 如果结点度为1，则该结点只有左孩子，不存在只有右子树的情况
     5. 同样结点数的二叉树，完全二叉树的深度最小

二叉树的性质

在二叉树的第i层上至多有2的(i-1)次方个结点

深度为k的二叉树至多有2的k次方-1个结点

对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

具有n个结点的完全二叉树的深度为[log2n]+1

如果对一棵有n个结点的完全二叉树的结点按层序编号,对任一结点i：

1. 如果i=1，则i是二叉树的根，无双亲；i>1,则其双亲是结点的[i/2]
2. 如果2i>n，则结点i无左孩子；否则其左孩子是结点2i
3. 如果2i+1>n，则结点i无右孩子；否则其右孩子是结点2i+1

二叉树的存储结构

顺序存储结构

二叉链表

• 设计一个数据域和两个指针域，这样的链表称为二叉链表

遍历二叉树

• 二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次，且只被访问一次

二叉树遍历方法

1. 前序遍历

• 规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树

2. 中序遍历

• 规则是若树为空，则空操作返回，否则从根点开始，中序遍历根结点的左子树，然后是访问根结点，最后访问根结点，最后中序遍历右子树

3. 后序遍历

• 规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点

4. 层序遍历

• 规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上到下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问

前序遍历算法

中序遍历算法

后序遍历算法

二叉树的建立

线索二叉树

线索二叉树原理

• 指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树就称为线索二叉树
• 我们对二叉树以某种次序遍历使其变为线索二叉树的过程称作是线索化
• 如果所用的二叉树需经常遍历或查找结点时需要某种遍历序列中的前驱和后继，那么采用线索二叉链表的存储结构就是非常不错的选择

树、森林与二叉树的转换

树转换为二叉树

1. 加线，在所有的兄弟结点之间加一条线
2. 去线，对树中每一个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线
3. 层次调整

森林转换为二叉树

1. 把每棵树转换为二叉树
2. 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线链接起来

二叉树转换为树

1. 加线，左孩子的n个右孩子结点都作为此结点的孩子
2. 去线，删除原二叉树中所有结点与其右孩子结点的连线
3. 层次调整

二叉树转换为森林

1. 从根结点开始，若右孩子存在，则把右孩子的结点的连线删除，直到所有的右孩子连线都删除为止
2. 将每棵分离的二叉树转换为树

赫夫曼树及其应用

赫夫曼树定义及其原理

• 从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度
• 树的路径长度就是从树根到每一个结点的路径长度之和
• 带权路径长度WPL最小的二叉树称做赫夫曼树
• 算法描述：
  1. 根据给定的n个权值，构成n棵二叉树的集合
  2. 在集合中选定两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树
  3. 在集合中删除，将新树加到集合中
  4. 重复2.3.最后只剩一棵

赫夫曼编码

• 左为0，右为1
• 若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码
• **一般地，设需要编码的字符集{d1...dn}，各个字符在电文中出现的次数或频率集合为{w1...wn}，以d1...dn作为叶子结点，以w1...wn作为相应的叶子结点的权值来构造一棵赫夫曼树，左分支为0，右分支为1，则从根结点到叶子结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，这就是赫夫曼编码