|
|
|
|
|
树是非线性结构，存储树时，须把树中结点之间存在的关系反映在树的存储结构中。树有很多存储结构，这里仅介绍最常用的两种。
|
|
|
|
|
|
树的标准存储结构由结点的数据和指向子结点的指针数组组成；对于度为M的树，其指针数组中的元素个数为M。
|
|
|
|
|
|
由于树的带逆存储结构需要一个从子结点指向父结点的指针，因而该结构在标准存储结构的基础上，需要在树的结点中增加一个指向其双亲结点位置的指针。
|
|
|
|
树的遍历是树的基本操作之一，也是最重要的操作之一。树的遍历含义是指：按照某种要求依次访问树中的每个结点，每个结点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
|
|
|
|
（1）树的前序遍历。首先访问根结点，然后从左到右前序遍历根结点的各棵子树。树的前序遍历递归算法如下：
|
|
|
|
|
|
若利用栈来记录当前未访问完的子树的根结点指针，则前序遍历的非递归算法如下：
|
|
|
|
|
|
（2）树的后序遍历。树的后序遍历的基本思想是：先依次遍历每棵子树，然后访问根结点，与后序遍历二叉树相同。树的后序遍历递归算法如下：
|
|
|
|
|
|
（3）树的中序遍历。树的中序遍历的基本思想是：先左子树，遍历根结点，然后依次遍历其他各棵子树，类似二叉树的中序遍历。树的中序遍历递归算法如下：
|
|
|
|
|
|
|
|
二叉树是结点的集合，这个集合或者为空，或者是由一个根和两棵互不相交的被称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树，且有左右之分，次序不能颠倒。
|
|
|
|
二叉树是一种重要的树型结构，但不是树的特例，其有5种形态，分别为：空（二叉树）；只有根结点；根结点和左子树；根结点和右子树；根结点和左右子树。
|
|
|
|
二叉树与树的区别：二叉树可以为空，每个结点子树不超过2个，而树至少有一个结点且结点子树无限制。
|
|
|
|
|
|
|
|
性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。
|
|
|
|
性质2：深度为k的二叉树至多有2k-1个结点（k≥1）。
|
|
|
|
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0= n2+1。
|
|
|
性质4：具有n个结点的完全二叉树的深度为 。
|
|
|
|
性质5：如果有n个结点的完全二叉树，对任一结点i(1
|
|
|
.如果i=1，则i为根，无双亲；若i>1，则i的双亲为 。
|
|
|
|
|
|
.如果2i+1>n，则无右孩子，否则右孩子为2i+1。
|
|
|
|
二叉树的有关性质可推广到k叉树，如：一棵含有n个结点的二叉树共含有n+1个空指针；而一棵含有n个结点的三叉树共含有2n+1个空指针。推而广之，一棵含有n个结点的k叉树共含有(k-1)n+1个空指针。
|
|
|
|
不难看出，在k叉树的第i层上至多有ki-1个结点（i≥1）；深度为H的k叉树至多有(kH-1)/(k-1)个结点(H≥1)。
|
|
|
|
同理，可得含N个结点和N个叶子结点的完全三叉树的高度分别为：
|
|
|
|
|
|
|
（1）设含N个结点的完全三叉树的高度为H，则1+3+…+3H-2+1≤N≤1+3+…+3H-1，3H-1≤2N-1≤3H-2，即 。
|
|
|
|
（2）设含N个叶子结点的完全三叉树的高度为H，则3H-2≤N≤3H-1，即
|
|
|
|
|
可进一步推广，含N个结点的完全k叉树的高度为 。
|
|
|
|
|
|
二叉树的遍历是其操作的重点，通常采用的递归算法不难实现和理解。但要实现二叉树遍历的非递归则有一定的难度，因而是理解二叉树遍历的难点。
|
|
|
|
由于很多程序员考题中都隐含地利用二叉树遍历的非递归算法，如：求二叉树中某个结点的祖先等，因而必须牢固地掌握二叉树的3种遍历的非递归算法。本质上，程序员考题中不是要考生遍历二叉树中的所有结点，而是遍历满足某种条件的结点并输出，在成功找到答案之前需要保留访问过的部分结点信息，因而须借助栈和队列等重要的数据结构。
|
|
|
|
二叉树的前序、中序和后序遍历的非递归算法分别如下所述。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
例如，在以二叉链表为存储结构的二叉树中，打印数据域值为x的结点（假定结点值不相同），并打印x的所有祖先的数据域值。
|
|
|
|
解决此问题的算法思想是：若在查找某结点的过程中，记下其祖先结点，则可以实现本问题要求。能实现这种要求的数据结构是栈，故设置一个栈用于装入x结点的所有祖先。而这种查找只有用非递归的后序遍历。
|
|
|
|
|
|
|
|
|
|
以二叉链表作为存储结构时，只能找到左、右子树信息，不能直接得到结点在任一序列中的前驱和后继信息，最简单的方法是每个结点上增加两个指针域，但有点浪费。其实，n个结点的二叉链表中必定存在n+1个空链域，因此可用这些链域来存放结点的前驱和后继信息。改进后的结点结构如下。
|
|
|
|
|
|
其中，ltag=0：表示lchild域指示结点的左子树。
|
|
|
|
|
|
rtag=0：表示rchild域指示结点的左子树。
|
|
|
|
|
|
|
|
|
|
以这种结构构成的二叉链表叫作线索链表，其中指向结点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫作线索化。
|
|
|
|
对给定的线索二叉树中的某个结点p，查找结点p的后继（中序），其特点为所有叶子结点的右链直接指示了后继，所有非终端结点的后继应是其右子树中第一个中序遍历的结点。
|
|
|
|
对给定的线索二叉树中的某个结点p，查找结点p的前驱（中序），其特点为若其左标志为1，则左链为线索，指示其前驱，否则其前驱为左子树上最后遍历的一个结点。
|
|
|
|
可见，对线索二叉树进行遍历可通过线索找到相应的前驱和后继，而无须进行递归。
|
|
|
|
例如，对给定的中序线索化二叉树，查找结点*p的中序后继。在中序线索二叉树中，查找p指针的结点，其后继分为两种情况：若p->rtag=1，则p->rchild，即指向其后继结点；若p->rtag=0，则*p结点的中序后继必为其右子树中第一个中序遍历到的结点，即从*p的右子树开始，沿着左指针链向下找，直到找到一个没有左子树的结点，该结点就是*p的右子树中"最左下"的结点。其算法如下：
|
|
|
|
|
|
|
|
由于树或森林可借用孩子兄弟表示法实现与二叉树的转换，所以只要研究二叉树的特性就行了，而无须对树或森林单独进行深入的讨论。
|
|
|
|
这里仅给出森林和二叉树的转换算法，树和二叉树的转换算法类似。
|
|
|
|
|
|
|
|
设F={T1，T2，…，Tn}是森林，对应的二叉树B={root，LB，RB}，则：
|
|
|
|
|
|
（2）若F非空，即n>0，则二叉树的根为T1的根，其左子树是从T1中根结点的子树森林F={T11，T12，…，T1n}转换而成的二叉树；其右子树是从森林F={T2，T3，…，Tn}转换而成的二叉树。
|
|
|
|
|
|
若B是一棵二叉树，根为T，L为左子树的根，R为右子树的根，则其相应的森林F{B}由下列步骤形成。
|
|
|
|
|
|
（2）若B非空，则B的根结点T为{T1，T2，…，Tn}的根结点，B[L]构成了T1的不相交的子树集合{T11，T12，…，T1n}；B[R]构成了森林中其他的树T2，…，Tn。
|
|
|
|
|
|
建立二叉树的方法有很多，如：按完全二叉树的形式输入字符序列，其中空格表示相应的子树为空。
|
|
|
|
近年来，在程序员考试中经常出现的二叉树建立为：已知二叉树的后序序列和中序序列或已知二叉树的前序序列和中序序列，要求考生确定一棵二叉树。
|
|
|
|
例如，一棵二叉树的中序序列和后序序列分别是DCBAEFG和DCBGFEA，请给出该二叉树的前序序列。该题可通过后序遍历确定二叉树的根结点，然后找到该数据值在前序序列中的位置，并用该位置的左部序列和后序序列中的相应序列构造左子树，用该位置的右部序列和后序序列中的相应序列构造右子树，如此不断地递归构造即可得到二叉树。建立的二叉树如下图所示。
|
|
|
|
|
|
|
|
而且，该题还可以引申到要考生证明已知二叉树的前序序列和中序序列，可唯一确定一棵二叉树；或要求考生针对已知二叉树的前序序列和中序序列，写出建立一棵二叉树的算法等。同时，要求考生证明已知二叉树的前序序列和后序序列，不能唯一确定一棵二叉树。
|
|
|
|
当然还可以通过给定的广义表建立二叉树等。可见，建立二叉树的方法很多，只要考生掌握了二叉树递归定义的本质和输入形式就可以方便地建立二叉树。
|
|
|
|
|
|
|
|
.路径：由从树中一个结点到另一个结点之间的分支构成两结点之间的路径。
|
|
|
|
|
|
.树的路径长度：从树根到每一个结点的路径长度之和。
|
|
|
|
.结点的带权路径长度：从结点到根之间的路径长度与结点上权的乘积WkLk。
|
|
|
|
.树的带权路径长度：树中所有带权叶子结点的路径长度之和。
|
|
|
|
.哈夫曼树：假设有n个数值{W1，W2，…，Wn}，试构造一棵有n个叶子结点的二叉树，结点带权为W1，带权路径长度WPL最小的二叉树称哈夫曼树。
|
|
|
|
对下图给定的两棵二叉树，它们的带权路径长度分别如下。
|
|
|
|
|
|
|
|
（1）WPL=7*2+5*2+2*2+4*2=36。
|
|
|
|
（2）WPL=7*1+5*2+2*3+4*3=35。
|
|
|
|
|
|
|
|
（1）根据给定的n个数值{W1，W2，…，Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，左右子树均空。
|
|
|
|
（2）在F中选取两棵根结点的数值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的数值为其左右子树上根结点的数值之和。
|
|
|
|
（3）在F中删除这两棵树，同时将新得到的二叉树加入F中。
|
|
|
|
（4）重复步骤（2）、（3），直到F只含一棵树为止。
|
|
|
|
|
|
哈夫曼编码的设计思想是：若要设计长短不等的编码，则必须是任意一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。利用二叉树来设计二进制的前缀编码，设计长度最短的二进制前缀编码，以n种字符出现的频率作为权，由此得到的二进制前缀编码为哈夫曼编码。
|
|
|
|
|
|
求集合{1，2，…，n}的幂集问题是一个经典的问题。解决这个问题的最典型做法就是递归调用，传统的做法这里不再讨论。
|
|
|
|
如何利用树状结构这个参照系来设计求集合{1，2，…，n}的幂集算法是我们讨论的重点。对于给定的集合{1,2,3,4}，按幂集集合中的元素个数和字典次序建立的树如下图所示。
|
|
|
|
|
|
|
|
为了保持集合中元素的字典次序，可采用两种方法来求集合{1,2,3,4}的幂集集合：①采用前序遍历树；②按层次遍历树。特别要注意的是在设计求集合的幂集时并不建立真正的树，而是在考生的心里建立这样一个虚拟的树，并以这棵树为参照系。下面给出这两种方法的算法。
|
|
|
|
|
|
|
|
|
|
|
|
可见，灵活地应用树状结构及其遍历操作的思路，能有效地解决实际应用问题。
|
|
|
|
|
|
二叉树运算是数据结构的重要内容。为了加深对二叉树内容的理解，这里给出一些应用实例。为方便描述，二叉树的顺序存储结构用一维数组R来表示，而二叉链表的结点存储结构定义如下：
|
|
|
|
|
|
（1）以二叉链表为存储结构，写一算法用括号形式（key,LT,RT）打印二叉树，其中key是根结点数据，LT和RT分别是括号形式的左右子树。并且要求：空树不打印任何信息，一个结点x的树打印形式是x，而不应是（x,）的形式。代码如下：
|
|
|
|
|
|
|
|
|
|
|
|
将已知二叉树改建为中序线序树的算法的主要思路是：对二叉树进行中序遍历，若当前被访问结点的左子结点指针为空，则让它指向当前结点的前驱结点；若其前驱结点的右子结点指针为空，则让它指向当前结点。相应的算法如下：
|
|
|
|
|
