第五章 树和二叉树
Diese Notiz ist noch nicht ins Deutsche übersetzt – Sie lesen das chinesische Original.
一 树的基本概念术语
单选题
树（tree）是n（n>=0）个结点的有限集T，它或是空集（空树即n=0），或是非空集。对于任何一棵非空树：
- 有且仅有一个特定的称为根（Root）的结点，
- 当n>1时，其余的结点可分为m（m>0）个互不相干的有限集T1，T2，…,Tm,其中每个集合又是一棵树，并称为跟的子树。
填空题
树的表示方法有树形表示法，嵌套集合表示法，凹形表示法和广义表表示法四种。
单选题，填空题，解答题，树的常用术语如下：
- 结点的度和树的度：树的结点包含一个数据元素及若干个指向其子树的分支。一个结点拥有的子树称为该结点的度，一棵树中结点的最大度数称为该树的度。
- 叶子结点，分支结点和跟结点：度数为零的结点称为叶子结点或终端结点。度数不为零的结点称为非终端结点或分支结点。除根结点之外，分支结点也称为内部结点，而根结点又称为开始结点。
- 孩子结点和双亲结点：树中某个结点子树的根称为该结点的孩子，相应地，该结点称为孩子结点的双亲或父结点。
- 子孙结点和祖先结点：若在一棵树中存在着一个结点序列k1,k2,k3,…,kj使得ki是ki+1的父结点（1<=i<=j）,则称该结点序列是从k1到kj的一条路径。若树中结点ki到kj存在一条路径，则称结点ki是结点kj的祖先，结点kj是ki的子孙。
- 结点的层次和树的高度：树中结点的层次是从根开始算起，根为第一层，其余结点的层次等于其双亲结点的层数加一。树中结点的最大层次称为树的深度或高度。
- 有序树和无序树：如果将树中结点的各子树看成是从左至右依次有序且不能交换，则称该树为有序树，否则称为无序树。
- 森林：森林是m（m>=0）棵互不相交的树的集合。若将一棵树的跟结点删除，就得到该树的子树所构成的森林；如果将森林中所有树作为子树，用一个跟结点把子树都连起来，森林就变成一棵树。
二 二叉树
填空题
二叉树是n（n>=0）个结点的有限集合，它的每个结点至多只有两颗子树。它或者是空集，或者是由一个跟结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。
单选题，填空题，解答题
二叉树具有几个非常重要的性质，如下所述。
- 在二叉树的第i层上至多有2**（i-1）个结点（i>=1）。
- 深度为k的二叉树至多有2**k-1个结点（k>=1）。
- 对任何一棵二叉树T，若其终端结点数为n0，度数为2的结点数为n2，则n0=n2+1。
- 具有n个结点的完全二叉树的深度为 [log2n] + 1 或 （[log2(n+1)]）
单选题，填空题
- 一棵深度为k且有2**k - 1 个结点的二叉树称为满二叉树。这种树的特点是每一层上的结点数都达到最大值，因此不存在度数为1的结点，且所有叶子结点都在第k层上。
- 若一棵深度为k的二叉树，其前k-1层是一棵满二叉树，而最下面一层（即第k层）上的结点都集中在该层最左边的若干位置上，则称此二叉树为完全二叉树。
填空题
在二叉树的链式存储表示中，通常采用的方法是：每个结点设置三个域，即值域，左指针域和右指针域，用data表示值域，Ichild和rchild分别表示指向左右子树（孩子）的指针域，如下所示。
lchild | data | rchild |
三 二叉树的运算
单选题，填空题：二叉树的遍历
-
前序遍历二叉树的递归定义，若二叉树非空，则依次进行操作：
-
访问跟结点
-
前序遍历左子树
-
前序遍历右子树
-
中序遍历二叉树的递归定义，若二叉树非空，则依次进行操作：
-
中序遍历左子树
-
访问根结点
-
中序遍历右子树
-
后序遍历二叉树的递归定义，若二叉树非空，则依次进行操作：
-
后序遍历左子树
-
后序遍历右子树
-
访问根结点
四 线索二叉树
填空题
- 对于n个结点的二叉树，二叉树表中必定存在n+1个空指针，利用这些空指针域存放指向结点在某种遍历次序下的前趋和后继结点的指针，这种指向前趋和后继结点的指针称为“线索”，加上线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。
- 在一个线索二叉树中，为了区分一个结点的左，右孩子指针域是指向其孩子的指针还是指向其前趋和后继的线索，可在结点结构中增加两个线索标志域，一个是左线索标志域，用ltag表示，另一个是右线索标志域，用rtag表示。ltag和rtag只能取值0和1。增加线索标志域后的结点结构如下：
lchild | ltag | data | rtag | rchild |
其中：ltag = 0 lchild域指向结点的左孩子/1 lchild域指向结点的前趋
rtag = 0 rchild域指向结点的右孩子/1 rchild域指向结点的后继
我们把对一棵二叉线索链表结构中所有结点的空指针域按照某种遍历次序加线索的过程称为线索化。
五 树和森林
填空题
树的存储结构通常采用三种表示方法即双亲表示法，孩子链表法和孩子兄弟表示法。
单选题，解答题：树，森林和二叉树之间的相互转换
-
树，森林到二叉树的转换
-
一棵树转换成二叉树：首先在所有兄弟结点之间加一道连线，然后再对每个结点保留长子的连线，去掉该结点与其他孩子的连线。由于树根没有兄弟，所以转换后的二叉树，其根结点的右子树必为空。
-
一个森林转换为二叉树：先将森林中的每棵树转化成二叉树，然后再将各二叉树的跟结点看作是兄弟连在一起，形成一棵二叉树。
-
二叉树到树，森林的转换
二叉树转换成对应的树或森林：若二叉树中结点X是双亲Y的左孩子，则把X的有孩子，右孩子的右孩子，…，都与Y用连线连起来，最后去掉所有双亲到右孩子的连线，即可得到对应的树或森林。
填空题
- 树中常用的两种遍历方法，前序（先根次序）遍历和后序（后续次序）遍历。
- 森林中常用的两种遍历方法：前序遍历和后序遍历。
六 哈夫曼树及其应用
填空题，解答题
在许多应用中，常常将树中的结点赋上一个具有某种意义的实数，我们称此实数为该结点的权。而从树跟结点到某结点之间的路径长度与该结点上权的乘积称为该结点的带权路径长度，树中所有叶子结点的带权路径长度之和称为树的带权路径长度，通常记为
WPL =
其中，n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。在权值为w1,w2,…,wn的n个叶结点构成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。
解答题，哈夫曼算法的思想是：
- 根据与n个权值 {w1, w2, …, wn} 对应的n个结点构成n棵二叉树的森林F={T1, T2, …, Tn}，其中每棵二叉树Ti都只有一个权值为wi的跟结点，其中左，右树均为空。
- 在森林F中选出两棵跟结点的权值最小的树作为一棵树的左，右子树，且置新树的附加跟结点的权值为其左，右子树上的根结点的权值之和。
- 从F中删除这两棵树，同时把新树加入到F中。
- 重复步骤（2）（3），直到F中只有一棵树为止，次树便是哈夫曼树。
填空题
- 若设计一种长短不等的编码，则必须保证任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码。
- 利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从跟到每个叶子都有一条路径，对路径上的各分支约定指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，每条路径上的“0”，“1”的序列作为各个叶子结点对应的字符编码，这就是哈夫曼编码。