|
|
|
|
|
|
|
|
|
.除根外的其他节点被分成n（n≥0）个不相交的集合T1,T2, …,Tn，其中每个集合本身是一棵树，树T1,T2, …,Tn称为根的子树。
|
|
|
|
这是一个递归定义，即在树的定义中又用到树的概念，它指出了树的固有特性，具有一个节点的树必然由根组成，而具有n>1个节点的树则借助于小于n个节点的树来定义。特别要注意的是递归定义中各子树T1,T2, …,Tn的相对次序是重要的，即是有序的。
|
|
|
|
|
|
|
|
|
|
.度为m的树中第i层上至多有mi-1个节点（i≥1）。
|
|
|
|
.高度为h的m叉树至多有（mh-1）/（m-1）个节点。
|
|
|
|
.具有n个节点的m叉树的最小高度为|logm（n（m-1）+1）|。
|
|
|
|
树还包含树的度、节点数及叶子节点数等。关于如何对给定的树求出满足某种条件的树的节点数和叶子节点数等问题，下面列举两个例子来加以说明。
|
|
|
|
例1：已知一棵度为m的树中有N1个度为1的节点，N2个度为2的节点，……，Nm个度为m的节点。试问该树中有多少个叶子节点？
|
|
|
解决该问题的关键是将树的节点数和树中各节点的度联系起来。若设该树中叶子节点个数为N0，则该树节点个数为 ，因该树节点个数又为 ，故
|
|
|
 ，即
|
|
|
|
例2：已知某度为k的树中，其度为0, 1, 2, …,k-1的节点数分别为n0,n1,n2, …,nk-1，求该树的节点总数。
|
|
|
|
|
|
|
|
而树的分支数（或连线数），即n-1为：n-1=n1+2n2+（k-1）nk-1+knk，故
|
|
|
|
|
|
|
|
|
|
树是非线性的结构，存储树时，须把树中节点之间存在的关系反映在树的存储结构中。树有很多存储结构，这里仅介绍最常用的两种。
|
|
|
|
|
|
树的标准存储结构由节点的数据和指向子节点的指针数组组成；对于度为M的树，其指针数组中的元素个数为M。
|
|
|
|
|
|
由于树的带逆存储结构需要一个从子节点指向父节点的指针，因而该结构在标准存储结构的基础上，需要在树的节点中增加一个指向其双亲节点位置的指针。
|
|
|
|
|
|
树的遍历是树的基本操作之一，也是最重要的操作之一。树的遍历含义是指：按照某种要求依次访问树中的每个节点，每个节点均被访问一次且仅被访问一次。常用的树的遍历方法可分为前序遍历、后序遍历和中序遍历。
|
|
|
|
|
|
首先访问根节点，然后从左到右前序遍历根节点的各棵子树。树的前序遍历递归算法如下：
|
|
|
|
|
|
若利用栈来记录当前未访问完的子树的根节点指针，则前序遍历的非递归算法如下：
|
|
|
|
|
|
|
|
树的后序遍历的基本思想是：先依次遍历每棵子树，然后访问根节点，与后序遍历二叉树相同。树的后序遍历递归算法如下：
|
|
|
|
|
|
|
|
树的中序遍历的基本思想是：先左子树，遍历根节点，然后依次遍历其他各棵子树，类似二叉树的中序遍历。树的中序遍历递归算法如下：
|
|
|
|
|
|
|
|
二叉树是节点的集合，这个集合或者为空，或者是由一个根和两棵互不相交的被称为左子树和右子树的二叉树组成。二叉树中的每个节点至多有两棵子树，且有左右之分，次序不能颠倒。
|
|
|
|
二叉树是一种重要的树型结构，但不是树的特例，其有5种形态，分别为：空（二叉树）；只有根节点；根节点和左子树；根节点和右子树；根节点和左右子树。
|
|
|
|
二叉树与树的区别：二叉树可以为空，每个节点子树不超过两个，而树至少有一个节点且节点子树无限制。
|
|
|
|
|
|
|
|
性质1在二叉树的第i层上至多有2i-1个节点（i≥1）。
|
|
|
|
性质2深度为k的二叉树至多有2k-1个节点（k≥1）。
|
|
|
|
性质3对任何一棵二叉树T，如果其终端节点数为n0，度为2的节点数为n2，则n0=n2+1。
|
|
|
|
性质4具有n个节点的完全二叉树的深度为[log2n]+1。
|
|
|
|
性质5如果有n个节点的完全二叉树，对任一节点i（1<i≤n）满足：
|
|
|
|
.如果i=1，则i为根，无双亲；若i>1，则i的双亲为[i/2]。
|
|
|
|
|
|
.如果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，即H=[log32N-1]+1。
|
|
|
|
（2）设含N个叶子节点的完全三叉树的高度为H，则3H-2≤N≤3H-1，即
|
|
|
|
|
|
|
|
|
|
|
|
二叉树的遍历是操作的重点，通常采用的递归算法不难实现和理解。但要实现二叉树遍历的非递归则有一定的难度，因而是理解二叉树遍历的难点。
|
|
|
|
由于很多程序员考题中都隐含地利用二叉树遍历的非递归算法，如求二叉树中某个节点的祖先等，因而必须牢固地掌握二叉树的三种遍历的非递归算法。本质上，程序员考题中不是要考生遍历二叉树中的所有节点，而是遍历满足某种条件的节点并输出，在成功找到答案之前需要保留访问过的部分节点信息，因而须借助栈和队列等重要的数据结构。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
例如，在以二叉链表为存储结构的二叉树中，打印数据域值为x的节点（假定节点值不相同），并打印x的所有祖先的数据域值。
|
|
|
|
解决此问题的算法思想是：若在查找某节点的过程中，记下其祖先节点，则可实现本问题要求。能实现这种要求的数据结构是栈，故设置一个栈用于装入x节点的所有祖先，而这种查找只有用非递归的后序遍历。
|
|
|
|
|
|
|
|
|
|
以二叉链表作为存储结构时，只能找到左、右子树信息，不能直接得到节点在任一序列中的前驱和后继信息，最简单的方法是每个节点上增加两个指针域，但有点浪费。其实，n个节点的二叉链表中必定存在n+1个空链域，因此可用这些链域来存放节点的前驱和后继信息。改进后的节点结构如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
以这种结构构成的二叉链表叫线索链表，其中指向节点前驱和后继的指针叫线索。加上线索的二叉树叫线索二叉树。对二叉树以某种次序遍历使其成为线索二叉树的过程叫线索化。
|
|
|
|
对给定的线索二叉树中的某个节点p，查找节点p的后继（中序），其特点为所有叶子节点的右链直接指示了后继，所有非终端节点的后继应是其右子树中第一个中序遍历的节点。
|
|
|
|
对给定的线索二叉树中的某个节点p，查找节点p的前驱（中序），其特点为若其左标志为"1"，则左链为线索，指示其前驱，否则其前驱为左子树上最后遍历的一个节点。
|
|
|
|
可见，对线索二叉树进行遍历可通过线索找到相应的前驱和后继，而无须递归进行。
|
|
|
|
例如，对给定的中序线索化二叉树，查找节点*p的中序后继。在中序线索二叉树中，查找p指针的节点，其后继分为两种情况：若p→rtag=1，则p→rchild，即指向其后继节点；若p→rtag=0，则*p节点的中序后继必为其右子树中第一个中序遍历到的节点，即从*p的右子树开始，沿着左指针链向下找，直到找到一个没有左子树的节点，该节点就是*p的右子树中"最左下"的节点。其算法如下：
|
|
|
|
|
|
|
|
由于树或森林可借用孩子兄弟表示法实现与二叉树的转换，因而我们只要研究二叉树的特性就行了，而无须对树或森林单独进行深入的讨论。
|
|
|
|
这里仅给出森林和二叉树的转换算法，树和二叉树的转换算法类似。
|
|
|
|
|
|
|
|
设T=｛T1,T2,…，Tn｝是森林，对应的二叉树B={root, LB, RB｝，则：
|
|
|
|
|
|
（2）若T非空，即n>0，则二叉树的根为T1的根，其左子树是从T1中根节点的子树森林T=｛T11,T12，…，T1n}转换而成的二叉树；其右子树是从森林T=｛T2,T3，…,Tn｝转换而成的二叉树。
|
|
|
|
|
|
若B是一棵二叉树，根为T，L为左子树的根，R为右子树的根，则其相应的森林T｛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,）的形式。相应的算法如下：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
将已知二叉树改建为中序线序树算法的主要思路是：对二叉树进行中序遍历，若当前被访问节点的左子节点指针为空，则让它指向当前节点的前驱节点；若其前驱节点的右子节点指针为空，则让它指向当前节点。相应的算法如下：
|
|
|
|
|
