《第5章树和二叉树.ppt》由会员分享，可在线阅读，更多相关《第5章树和二叉树.ppt（126页珍藏版）》请在三一办公上搜索。
1、,数 据 结 构,办公室：B315电话：82878095EmaIL:,计算机系教师 段恩泽,第5章 树和二叉树,树型结构是一对多的非线性结构，非常类似于自然界中的树，数据元素之间既有分支关系，又有层次关系。树型结构在现实世界中广泛存在，如家族的家谱、一个单位的行政机构组织等都可以用树型结构来形象地表示。树型结构在计算机领域中也有非常广泛的应用，如Windows操作系统中对磁盘文件的管理、编译程序中对源程序的语法结构的表示都采用树型结构。在数据库系统中，树型结构也是数据的重要组织形式之一。,5.1树,5.1.1树的定义 树(Tree)是n(n0)个相同类型的数据元素的有限集合。树中的数据元素叫结
2、点。n=0的树称为空树；对于n0的任意非空树T有：（1）有且仅有一个特殊的结点称为树的根(Root)结点，根没有前驱结点；（2）若n1，则除根结点外，其余结点被分成了m(m0)个互不相交的集合T1，T2，Tm，其中每一个集合Ti(1im)本身又是一棵树。树T1，T2，Tm称为这棵树的子树。由树的定义可知，树的定义是递归的，用树来定义树。因此，树（以及二叉树）的的许多算法都使用了递归。,树的形式定义为：树(Tree)简记为T，是一个二元组，T=(D,R)其中：D是结点的有限集合，R是结点之间关系的有限集合。,下图是一棵具有10个结点的树，即T=A,B,C,D,E,F,G,H,I,J。结点A是树T
3、的根结点，根结点A没有前驱结点。除A之外的其余结点分成了三个互不相交的集合：T1=B,E,F,G，T2=C,H，T3=D,I,J，分别形成了三棵子树，B、C和D分别成为这三棵子树的根结点，因为这三个结点分别在这三棵子树中没有前驱结点。,从树的定义和上图的示例可以看出，树具有下面两个特点：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点；（2）树中的所有结点都可以有零个或多个后继结点。实际上，第（1）个特点表示的就是树型结构的“一对多关系”中的“一”，第（2）特点表示的是“多”。,由此特点可知，下图所示的都不是树。,A,B,C,D,E,F,G,H,I,J,A,C,D,H,
4、I,J,（c）,5.1.2 树的相关术语 结点：表示树中的数据元素，由数据项和数据元素之间的关系组成。在图5.1中，共有10个结点。结点的度：结点所拥有的子树的个数，在图5.1中，结点A的度为3。树的度：树中各结点度的最大值。在图5.1中，树的度为3。叶子结点：度为0的结点，也叫终端结点。在图5.1中，结点E、F、G、H、I、J都是叶子结点。分支结点：度不为0的结点，也叫非终端结点或内部结点。在图5.1中，结点A、B、C、D是分支结点。孩子：结点子树的根。在图5.1中，结点B、C、D是结点A的孩子。双亲：结点的上层结点叫该结点的双亲。在图5.1中，结点B、C、D的双亲是结点A。祖先：从根到该结
5、点所经分支上的所有结点。在图5.1中，结点E的祖先是A和B。子孙：以某结点为根的子树中的任一结点。在图5.1中，除A之外的所有结点都是A的子孙。,兄弟：同一双亲的孩子。在图5.1中，结点B、C、D互为兄弟。结点的层次：从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1，其余结点的层次等于其双亲结点的层次加1。堂兄弟：同一层的双亲不同的结点。在图5.1中，G和H互为堂兄弟。树的深度：树中结点的最大层次数。在图5.1中，树的深度为3。无序树：树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。有序树：树中任意一个结点的各孩子结点有严格排列次序的树。二叉
6、树是有序树，因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。森林：m(m0)棵树的集合。自然界中的树和森林的概念差别很大，但在数据结构中树和森林的概念差别很小。从定义可知，一棵树有根结点和m个子树构成，若把树的根结点删除，则树变成了包含m棵树的森林。当然，根据定义，一棵树也可以称为森林。,5.1.3 树的逻辑表示 树的逻辑表示方法很多，这里只讲几种常见的表示方法。（1）直观表示法 它象日常生活中的树木一样。整个图就象一棵倒立的树，从根结点出发不断扩展，根结点在最上层，叶子结点在最下面。（2）凹入表示法 每个结点对应一个矩形，所有结点的矩形都左对齐，根结点用最长的矩形表示
7、，同一层的结点的矩形长度相同，层次越高，矩形长度越短。,（3）广义表表示法 用广义表的形式表示根结点排在最前面，用一对圆括号把它的子树结点括起来，子树结点用逗号隔开。上图的树的广义表表示如下：（A（B（E，F，G），C（H），D（I，J）（4）嵌套表示法 类似数学中所说的文氏图表示法，如下图所示。,5.1.4 树的基本操作 树的操作很多，比如访问根结点，得到结点的值、求结点的双亲结点、某个子结点和某个兄弟结点。又比如，插入一个结点包括插入一个结点作为某个结点的最左子结点、最右子结点等。删除结点也是一样。也可按照某种顺序遍历一棵树。在这些操作中，有些操作是针对结点的（访问父亲结点、兄弟结点或子结
8、点），有些操作是针对整棵树的（访问根结点、遍历树）。如果象前面几种数据结构用接口表示树的操作的话，就必须把结点类的定义写出来。但本章的重点不是树而是二叉树。所以，树的操作不用接口来表示，只给出操作的名称和功能。树的基本操作通常有以下几种：（1）Root()：求树的根结点，如果树非空，返回根结点，否则返回空。（2）Parent(t)：求结点t的双亲结点。如果t的双亲结点存在，返回双亲结点，否则返回空。,（3）Child(t,i)：求结点t的第i个子结点。如果存在，返回第i个子结点，否则返回空。（4）RightSibling(t)：求结点t第一个右边兄弟结点。如果存在，返回第一个右边兄弟结点，否则
9、返回空。（5）Insert(s,t,i)：把树s插入到树中作为结点t的第i棵子树。成功返回true，否则返回false。（6）Delete(t,i)：删除结点t的第i棵子树。成功返回第i棵子树的根结点，否则返回空。（7）Traverse(TraverseType)：按某种方式遍历树。（8）Clear()：清空树。（9）IsEmpty()：判断树是否为空树。如果是空树，返回true，否则返回false。（10）GetDepth()：求树的深度。如果树不为空，返回树的层次，否则返回0。,5.2 二叉树5.2.1 二叉树的定义 二叉树(Binary Tree)是n(n0)个相同类型的结点的有限集合。
10、n=0的二叉树称为空二叉树；对于n0的任意非空二叉树有：（1）有且仅有一个特殊的结点称为二叉树的根(Root)结点，根没有前驱结点；（2）若n1，则除根结点外，其余结点被分成了2个互不相交的集合TL，TR，而TL、TR本身又是一棵二叉树，分别称为这棵二叉树的左子树和右子树。,二叉树的形式定义为：二叉树(Binary Tree)简记为BT，是一个二元组，BT=(D,R)其中：D是结点的有限集合，R是结点之间关系的有限集合。,由树的定义可知，二叉树是另外一种树型结构，并且是有序树，它的左子树和右子树有严格的次序,若将其左、右子树颠倒，就成为另外一棵不同的二叉树。因此下图(a)和图(b)所示是不同的
11、二叉树。,A,B,C,D,A,B,C,D,(b),二叉树的形态共有5种：空二叉树、只有根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树和左、右子树非空的二叉树。二叉树的5种形态如图所示。,下面介绍两种特殊的二叉树。满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树，如图5.7(a)所示。由定义可知，对于深度为k的满二叉树的结点个数为2k-1。完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k，有n个结点的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树，如图5.7(b)所示。完全二叉树的特点是叶子结点只可
12、能出现在层次最大的两层上，并且某个结点的左分支下子孙的最大层次与右分支下子孙的最大层次相等或大1。,5.2.2 二叉树的性质 性质1 一棵非空二叉树的第i层上最多有2i-1个结点(i1)。证明：采用数学归纳法进行证明。当n=1时，二叉树只有1层，这一层只有根结点一个结点，所以第1层的结点数为21-1=1，结论成立。假设当n=N时结论成立，即第N层最多有2N-1个结点；当n=N+1时，根据二叉树的定义，第N层的每个结点最多有2个子结点，所以第N+1层上最多有2N-1*2=2N=2(N+1)-1个结点，结论成立。综上所述，性质1成立。,性质2 若规定空树的深度为0，则深度为k的二叉树最多有2k-1
13、个结点(k0)。证明：当k=0时，空树的结点数为20-1=0，结论成立。当深度为k(k0)时，由性质1可知，第i(1ik)层最多有2i-1个结点，所以二叉树的最多结点数是：,性质3 具有n个结点的完全二叉树的深度k为log2n+1。证明：根据性质2和完全二叉树的定义可知，当一棵完全二叉树的结点数为n、深度为k时，有 2k-1-1n2k-1 即 2k-1n2k 对不等式取对数，有 k-1log2nk 由于k是整数，所以有k=log2n+1。,性质4 对于一棵非空二叉树，如果度为0的结点数目为n0，度为2的结点数目为n2，则有n0=n2+1。证明：设n为二叉树的结点总数，n1二叉树中度为1的结点数
14、目，则有 n=n0+n1+n2(5-1)在二叉树中，除根结点外，其余结点都有惟一的一个进入分支。设B为二叉树中的分支总数，则有 B=n-1(5-2)这些分支由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出2个分支，所以有 B=n1+2 n2(5-3)综合上面3个式子，可以得到 n0=n2+1,性质5 对于具有n个结点的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则对于序号为i的结点，有：（1）如果i1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i=1，则该结点是根结点，无双亲结点。（2）如果2in，则该结点的左孩子结
15、点的序号为2i；若2in，则该结点无左孩子。（3）如果2i+1n，则该结点的右孩子结点的序号为2i+1；若2i+1n，则该结点无右孩子。,性质5的证明比较复杂，故省略。我们用实际例子检验性质5的正确性。对于图5.7(b)所示的完全二叉树，如果按照从上到下和从左到右的顺序对所有结点从1开始编号，则结点和结点序号的对应关系如下：,该完全二叉树的结点总数n=10。对于结点D，相应的序号为4，则结点D的双亲结点的序号为4/2=2，即结点B；左孩子结点的序号为2i=2*4=8，即结点H；右孩子结点的序号为2i+1=2*4+1=9，即结点I。对于结点E，相应的序号为5，则结点E的双亲结点的序号为5/2=2
16、，即结点B；左孩子结点的序号为2i=2*5=10，即结点J；右孩子结点的序号为2i+1=2*5+1=11n=10，即结点E没有右孩子。,5.2.3 二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、二叉链表存储结构和三叉链表存储结构。1、二叉树的顺序存储结构 对于一棵完全二叉树，由性质5可计算得到任意结点i的双亲结点序号、左孩子结点序号和右孩子结点序号。所以，完全二叉树的结点可按从上到下和从左到右的顺序存储在一维数组中，其结点间的关系可由性质5计算得到，这就是二叉树的顺序存储结构。图5.7(a)所示的二叉树的顺序存储结构为：,但是，对于一棵非完全二叉树，不能简单地按照从上到下和从左到
17、右的顺序存放在一维数组中，因为数组下标之间的关系不能反映二叉树中结点之间的逻辑关系。所以，应该对一棵非完全二叉树进行改造，增加空结点（并不存在的结点）使之成为一棵完全二叉树，然后顺序存储在一维数组中。图5.8(a)是图5.6(e)的完全二叉树形态，图5.8(b)是图5.8(a)的顺序存储示意图。,图5.8 一般二叉树的改造及其顺序存储示意图,显然，顺序存储对于需增加很多空结点才能改造为一棵完全二叉树的二叉树不适合，因为会造成空间的大量浪费。实际上，采用顺序存储结构，是对非线性的数据结构线性化，用线性结构来表示二叉树的结点之间的逻辑关系，所以，需要增加空间。一般来说，有大约一半的空间被浪费。最差
18、的情况是右单支树，如图5.9所示，一棵深度为k的右单支树，只有k个结点，却需要分配2k-1个存储单元。,图5.9 右单支树及其顺序存储示意图,2、二叉树的二叉链表存储结构 二叉树的二叉链表存储结构是指二叉树的结点有三个域：一个数据域和两个引用域，数据域存储数据，两个引用域分别存放其左、右孩子结点的地址。当左孩子或右孩子不存在时，相应域为空，用符号NULL或表示。结点的存储结构如下所示：,图5.10是图5.8(a)所示的二叉树的二叉链表示意图。图5.10(a)是不带头结点的二叉链表，图5.10(b)是带头结点的二叉链表。,图5.10 二叉树的二叉链表示意图,由图5.10所示的二叉树有4个结点，每
19、个结点中有两个引用，共有8个引用，其中3个引用被使用，5个引用是空的。由性质4可知：由n个结点构成的二叉链表中，只有n-1个引用域被使用，还有n+1个引用域是空的。,3、二叉树的三叉链表存储结构 使用二叉链表，可以非常方便地访问一个结点的子孙结点，但要访问祖先结点非常困难。可以考虑在每个结点中再增加一个引用域存放其双亲结点的地址信息，这样就可以通过该引用域非常方便地访问其祖先结点。这就是下面要介绍的三叉链表。二叉树的三叉链表存储结构是指二叉树的结点有四个域：一个数据域和三个引用域，数据域存储数据，三个引用域分别存放其左、右孩子结点和双亲结点的地址。当左、右孩子或双亲结点不存在时，相应域为空，用
20、符号NULL或表示。结点的存储结构如下所示：,图5.11是图5.8(a)所示的二叉树的三叉链表示意图。图5.11(a)是不带头结点的三叉链表，图5.11(b)是带头结点的三叉链表。,图5.11 二叉树的三叉链表示意图,5.2.4二叉链表存储结构的类实现 二叉树的二叉链表的结点类有3个成员字段：数据域字段data、左孩子引用域字段lChild和右孩子引用域字段rChild。二叉树的二叉链表的结点类的实现如图5.12所示。public class Node private T data;private Node lChild;private Node rChild;public Node(T va
21、l,Node lp,Node rp)data=val;lChild=lp;lChild=rp;,public Node(Node lp,Node rp)data=default(T);lChild=lp;rChild=rp;public Node(T val)data=val;lChild=null;rChild=null;public Node()data=default(T);lChild=null;rChild=null;,public T Data get return data;set value=data;,public Node LChild get return lChild;
22、set lChild=value;,public Node RChild get return rChild;set rChild=value;,图5.12二叉树的二叉链表的结点类的实现,不带头结点的二叉树的二叉链表比带头结点的二叉树的二叉链表的区别与不带头结点的单链表与带头结点的单链表的区别一样。下面只介绍不带头结点的二叉树的二叉链表的类BiTree。BiTree类只有一个成员字段head表示头引用。图5.13是BiTree类的实现。,public class BiTree private Node head;public Node Head get return head;set head
23、=value;,/构造器 public BiTree()head=null;/构造器 public BiTree(T val)Node p=new Node(val);head=p;/构造器 public BiTree(T val,Node lp,Node rp)Node p=new Node(val,lp,rp);head=p;,/判断是否是空二叉树 public bool IsEmpty()if(head=null)return true;else return false;/获取根结点 public Node Root()return head;,/获取结点的左孩子结点 public N
24、ode GetLChild(Node p)return p.LChild;/获取结点的右孩子结点 public Node GetRChild(Node p)return p.RChild;,/将结点p的左子树插入值为val的新结点，/原来的左子树成为新结点的左子树 public void InsertL(T val,Node p)Node tmp=new Node(val);tmp.LChild=p.LChild;p.LChild=tmp;/将结点p的右子树插入值为val的新结点，/原来的右子树成为新结点的右子树 public void InsertR(T val,Node p)Node tm
25、p=new Node(val);tmp.RChild=p.RChild;p.RChild=tmp;,/若p非空，删除p的左子树 public Node DeleteL(Node p)if(p=null)|(p.LChild=null)return null;Node tmp=p.LChild;p.LChild=null;return tmp;,/若p非空，删除p的右子树 public Node DeleteR(Node p)if(p=null)|(p.RChild=null)return null;Node tmp=p.RChild;p.RChild=null;return tmp;,/判断是
26、否是叶子结点 public bool IsLeaf(Node p)if(p!=null),图5.13 BiTree类的实现,5.2.5 二叉树的遍历 二叉树的遍历是指按照某种顺序访问二叉树中的每个结点，使每个结点被访问一次且仅一次。遍历是二叉树中经常要进行的一种操作，因为在实际应用中，常常要求对二叉树中某个或某些特定的结点进行处理，这需要先查找到这个或这些结点。实际上，遍历是将二叉树中的结点信息由非线性排列变为某种意义上的线性排列。也就是说，遍历操作使非线性结构线性化。,由二叉树的定义可知，一棵二叉树由根结点、左子树和右子树三部分组成，若规定D、L、R分别代表遍历根结点、遍历左子树、遍历右子树
27、，在二叉树的遍历方式有6种：DLR、DRL、LDR、LRD、RDL、RLD。由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以，只讨论三种方式：DLR（先序遍历）、LDR（中序遍历）和LRD（后序遍历）。除了这三种遍历方式外，还有一种方式：层序遍历。层序遍历是从根结点开始，按照从上到下、从左到右的顺序依次访问每个结点一次仅一次。,1、先序遍历（DLR）先序遍历的基本思想是：首先访问根结点，然后先序遍历其左子树，最后先序遍历其右子树。先序遍历的递归算法实现如下，注意：这里的访问根结点是把根结点的值输出到控制台上。当然，也可以对根结点作其它处理。public void PreOrder(
28、Node root)if(root=null)return;Console.WriteLine(0,root.Data);PreOrder(root.LChild);PreOrder(root.RChild);,2、中序遍历（LDR）中序遍历的基本思想是：首先中序遍历根结点的左子树，然后访问根结点，最后中序遍历其右子树。中序遍历的递归算法实现如下：public void InOrder(Node root)if(root=null)return;InOrder(root.LChild);Console.WriteLine(0,root.Data);InOrder(root.RChild);,3
29、、后序遍历（LRD）后序遍历的基本思想是：首先后序遍历根结点的左子树，然后后序遍历根结点的右子树，最后访问根结点。后序遍历的递归算法实现如下，public void PostOrder(Node root)if(root=null)return;PostOrder(root.LChild);PostOrder(root.RChild);Console.WriteLine(0,root.Data);,4、层序遍历（Level Order）层序遍历的基本思想是：由于层序遍历结点的顺序是先遇到的结点先访问，与队列操作的顺序相同。所以，在进行层序遍历时，设置一个队列,将根结点引用入队，当队列非空时，循
30、环执行以下三步：从队列中取出一个结点引用，并访问该结点；若该结点的左子树非空，将该结点的左子树引用入队；若该结点的右子树非空，将该结点的右子树引用入队；,层序遍历的算法实现如下：public void LevelOrder(Node root)if(root=null)return;CSeqQueue sq=new CSeqQueue(50);sq.In(root);,while(!sq.IsEmpty()Node tmp=sq.Out();Console.WriteLine(o,tmp);if(tmp.LChild!=null)sq.In(tmp.LChild);if(tmp.RChild!
31、=null)sq.In(tmp.RChild);,5.3 树与森林5.3.1 树的存储 在实际应用中，人们采用多种形式的存储结构来表示树，既有顺序存储结构，又有链式存储结构，但无论采用哪种存储结构，都要求存储结构不但能存储结点本身的信息，还能存储树中各结点之间的逻辑关系。1、双亲表示法 从树的定义可知，除根结点外，树中的每个结点都有惟一的一个双亲结点。根据这一特性，可用一组连续的存储空间（一维数组）存储树中的各结点。树中的结点除保存结点本身的信息之外，还要保存其双亲结点在数组中的位置（数组的序号），树的这种表示法称为双亲表示法。,由于树的结点只保存两个信息，所以树的结点用结构体PNode来表示
32、。结构中有两个字段：数据字段data和双亲位置字段pPos。而树类PTree只有一个成员数组字段nodes，用于保存结点。PNode和PTree都只给出了成员字段，没有给出其它成员，比如属性、构造器、成员方法等等，感兴趣的读者可以自己添加。树的双亲表示法的结点的结构如下所示：,树的双亲表示法的结点的结构体PNode和树类PTree的定义如下：public struct PNode public T data;public int pPos;public class PTree private PNode nodes;,树的双亲表示法如下图所示。图中pPos域的值为-1表示该结点是根结点，无双亲
33、结点。,树的双亲表示法对于实现Parent(t)操作和Root()操作非常方便。Parent(t)操作可以在常量时间内实现，反复调用Parent(t)操作，直到遇到无双亲的结点（其pPos值为-1）时，便找到了树的根，这就是Root()操作的执行过程。但要实现查找孩子结点和兄弟结点等操作非常困难，因为这需要查询整个数组。要实现这些操作，需要在结点结构中增设存放第1个孩子在数组中的序号的域和存放第1个兄弟在数组中的序号的域。,2、孩子链表表示法 孩子链表表示法也是用一维数组来存储树中各结点的信息。但结点的结构与双亲表示法中结点的结构不同，孩子链表表示法中的结点除保存本身的信息外，不是保存其双亲结
34、点在数组中的序号，而是保存一个链表的第一个结点的地址信息。这个链表是由该结点的所有孩子结点组成。每个孩子结点保存有两个信息，一个是每个孩子结点在一维数组中的序号，另一个是下一个孩子结点的地址信息。孩子结点的结构如下所示：,孩子结点类ChildNode的定义如下（与前面一样，只列出了成员字段）：public class ChildNode private int index;private ChildNode nextChild;树的孩子链表表示法的结点的结构如下所示：,树的孩子链表表示法的结点类CLNode的定义如下：public class CLNode private T data;pri
35、vate ChildNode firstChild;树类CLTree的定义如下：public class CLTree private Node nodes;,树的孩子链表表示法对于实现查找孩子结点等操作非常方便，但对于实现查找双亲结点、兄弟结点等操作则比较困难。,这是一种常用的数据结构，又称二叉树表示法，或二叉链表表示法，即以二叉链表作为树的存储结构。每个结点除存储本身的信息外，还有两个引用域分别存储该结点第一个孩子的地址信息和下一个兄弟的地址信息。树类CSTree只有一个成员字段head，表示头引用。树的孩子兄弟表示法的结点的结构如下所示：,树的孩子兄弟表示法的结点类CSNode的定义如下
36、：public class CSNode private T data;private CSNode firstChild;private CSNode nextSibling;树类CSTree的定义如下：public class CSTree private CSNode head;,树的孩子兄弟表示法如图所示:,树的孩子兄弟表示法对于实现查找孩子、兄弟等操作非常方便，但对于实现查找双亲结点等操作则非常困难。如果在树的结点中再增加一个域来存储孩子的双亲结点的地址信息，则就可以较方便地实现上述操作了。,5.3.2 树、森林与二叉树的转换 从树的孩子兄弟表示法可知，树可以用二叉链表进行存储，所以
37、，二叉链表可以作为树和二叉树之间的媒介。也就是说，借助二叉链表，树和二叉树可以相互进行转换。从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。并且，如果设定一定的规则，就可用二叉树来表示森林，森林和二叉树也可以相互进行转换。,1、树转换为二叉树 由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。如图5.1所示的树，根结点A有三个孩子B、C、D，规定结点B是结点A的第一个孩子，结点C是结点A的第2个孩子，结点D是结点A的第3个孩子。,将树转换成二叉树的步骤是：（1）加线。就是在所有兄弟结点之间加一条连线。（2）抹线。就是对树中的每个结
38、点，只保留它与第一个孩子结点之间的 连线，删除它与其它孩子结点之间的连线。（3）旋转。就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构成次分明。,图5.17是图5.1所示的树转换为二叉树的转换过程示意图。,图5.17 树转换为二叉树的过程示意图,2、森林转换为二叉树 森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。将森林转换为二叉树的步骤是：（1）先把每棵树转换为二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起
39、来后得到的二叉树就是由森林转换得到的二叉树。,图5.18是森林转换为二叉树的转换过程示意图。,图5.18 森林转换为二叉树的转换过程示意图,3、二叉树转换为树 二叉树转换为树是树转换为二叉树的逆过程，其步骤是：（1）若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来。（2）删除原二叉树中所有结点与其右孩子结点的连线。（3）整理（1）和（2）两步得到的树，使之结构层次分明。,图5.19是二叉树转换为树的过程示意图。,图5.19 二叉树转换为树的过程示意图,4、二叉树转换为森林 二叉树转换为森林比较简单，其步骤如下
40、：（1）先把每个结点与右孩子结点的连线删除，得到分离的二叉树。（2）把分离后的每棵二叉树转换为树。（3）整理第（2）步得到的树，使之规范，这样得到森林。,5.3.3 树和森林的遍历 1、树的遍历 树的遍历通常有两种方式。（1）先序遍历，即先访问树的根结点，然后依次先序遍历树中的每棵子树。（2）后序遍历，即先依次后序遍历树中的每棵子树，然后访问根结点。对图5.1所示的树进行先序遍历所得到的结点序列为 A B E F G C H D I J 对此树进行后序遍历得到的结点序列为 E F G B H C I J D A,根据树与二叉树的转换关系以及二叉树的遍历定义可以推知，树的先序遍历与其转换的相应的
41、二叉树的先序遍历的结果序列相同；树的后序遍历与其转换的二叉树的中序遍历的结果序列相同；树的层序遍历与其转换的二叉树的后序遍历的结果序列相同。因此，树的遍历算法可以采用相应的二叉树的遍历算法来实现。另外，在后面讲图的广度优先遍历算法中要提到树的层序遍历算法。树的层序遍历算法与二叉树的层序遍历算法类似，也是从树的根结点开始，按从从上到下从左到右的顺序进行遍历。,2、森林的遍历 森林的遍历有两种方式。（1）先序遍历，即先访问森林中第一棵树的根结点，然后先序遍历第一棵树中的每棵子树，最后先序遍历除第一棵树之后剩余的子树森林。（2）中序遍历，即先中序遍历森林中第一棵树的根结点的所有子树，然后访问第一棵树
42、的根结点，最后中序遍历除第一棵树之后剩余的子树森林。图5.18（a）所示的森林的先序遍历的结点序列为 A B C D E F G H J I 此森林的中序遍历的结点序列为 B C D A F E J H I G 由森林与二叉树的转换关系以及森林与二叉树的遍历定义可知，森林的前序遍历和中序遍历与所转换得到的二叉树的先序遍历和中序遍历的结果序列相同。,5.4哈夫曼树5.4.1哈夫曼树的基本概念 首先给出定义哈夫曼树所要用到的几个基本概念。（1）路径：从树中的一个结点到另一个结点之间的分支构成这两个结点间的路径。（2）路径长度：路径上的分支数。（3）树的路径长度：从树的根结点到每个结点的路径长度之和
43、。在结点数目相同的二叉树中，完全二叉树的路径长度最短。（4）结点的权：在一些应用中，赋予树中结点的一个有实际意义的数。（5）结点的带权路径长度：从该结点到树的根结点的路径长度与该结点的权的乘积。,（6）树的带权路径长度（WPL）：树中所有叶子结点的带权路径长度之和，记为,其中，Wk为第k个叶子结点的权值，Lk为第k个叶子结点的路径长度。,在图5.19(a)所示的二叉树中，结点B的路径长度为1，结点C和D的路径长度为2，结点E、F和G的路径长度为3，结点H的路径长度为4，结点I的路径长度为5。该树的路径长度为：1+2*2+3*3+4+5=23。如果结点B、C、D、E、F、G、H、I的权分别是1、
44、2、3、4、5、6、7、8，则这些结点的带权路径长度分别是1*1、2*2、2*3、3*4、3*5、3*6、4*7、5*8，该树的带权路径长度为3*5+3*6+5*8=73。,图5.20 具有不同带权路径长度的二叉树,哈夫曼树(Huffman Tree)，又叫最优二叉树，指的是对于一组具有确定权值的叶子结点的具有最小带权路径长度的二叉树。在图5.20所示的的四棵二叉树，都有4个叶子结点，其权值分别为1、2、3、4，它们的带权路径长度分别为(a)WPL=12+22+32+42=20(b)WPL=11+22+33+43=28(c)WPL=13+23+32+41=19(d)WPL=21+12+33+4
45、3=29,那么，如何构造一棵哈夫曼树呢？哈夫曼最早给出了一个带有一般规律的算法，俗称哈夫曼算法。现叙述如下：（1）根据给定的n个权值w1,w2,wn构造n棵只有根结点的二叉树集合F=T1,T2,Tn。（2）从集合F中选取两棵根结点的权最小的二叉树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树根结点权值之和。（3）在集合F中删除这两棵树，并把新得到的二叉树加入到集合F中。（4）重复上述步骤，直到集合中只有一棵二叉树为止，这棵二叉树就是哈夫曼树。,图5.21是给出了前面提到的叶子结点权值集合W=1,2,3,4的哈夫曼树的构造过程。由二叉树的性质4和哈夫曼树的特点可知，一
46、棵有n个叶子结点构造的哈夫曼树共有2n-1个结点。,图5.21 哈夫曼树的构造过程,5.4.2哈夫曼树类的实现 由哈夫曼树的构造算法可知，用一个数组存放原来的n个叶子结点和构造过程中临时生成的结点，数组的大小为2n-1。所以，哈夫曼树类HuffmanTree中有两个成员字段：data数组用于存放结点，leafNum表示哈夫曼树叶子结点的数目。结点有四个域，一个域weight，用于存放该结点的权值；一个域lChild，用于存放该结点的左孩子结点在数组中的序号；一个域rChild，用于存放该结点的右孩子结点在数组中的序号；一个域parent，用于判定该结点是否已加入哈夫曼树中。哈夫曼树结点的结构如
47、下所示。,所以，结点类Node有4个成员字段，weight表示该结点的权值，lChild和rChild分别表示左、右孩子结点在数组中的序号，parent表示该结点是否已加入哈夫曼树中，如果parent的值为-1，表示该结点未加入到哈夫曼树中。当该结点已加入到哈夫曼树中时，parent的值为其双亲结点在数组中的序号。结点类Node的定义如图5.22：public class Node private int weight;private int lChild;private int rChild;private int parent;,public int Weight get return w
48、eight;set weight=value;,public int LChild get return lChild;set lChild=value;,public int RChild get return rChild;set rChild=value;,public int Parent get return parent;set parent=value;,/构造器 public Node()weight=0;lChild=-1;rChild=-1;parent=-1;/构造器 public Node(int w,int lc,int rc,int p)weight=w;lChil
49、d=lc;rChild=rc;parent=p;图5.22 结点类Node的定义,哈夫曼树类HuffmanTree中只有一个成员方法Create，它的功能是输入n个叶子结点的权值，创建一棵哈夫曼树。哈夫曼树类HuffmanTree的实现如图5.23所示。public class HuffmanTree private Node data;private int leafNum;,public Node thisint index get return dataindex;set dataindex=value;,public int LeafNum get return leafNum;set
50、 leafNum=value;public HuffmanTree(int n)data=new Node2*n-1;leafNum=n;,public void Create()int m1;int m2;int x1;int x2;/输入n个叶子结点的权值 for(int i=0;i this.leafNum;+i)datai.Weight=Console.Read();,/处理n个叶子结点，建立哈夫曼树 for(int i=0;i this.leafNum-1;+i)max1=max2=Int32.MaxValue;tmp1=tmp2=0;/在全部结点中找权值最小的两个结点 for(in
