数据结构：第六章 树与二叉树

1、六、树与二叉树六、树与二叉树6.1 6.1 树的定义树的定义数数据据结结构构线性结构：在数据结构中每个结点线性结构：在数据结构中每个结点都只有一个直接前驱或直接后继的都只有一个直接前驱或直接后继的结点。结点。非线性结构：在数据结构中至少存非线性结构：在数据结构中至少存在一个具有两个或两个以上直接前在一个具有两个或两个以上直接前驱或直接后继的结点。驱或直接后继的结点。六、树与二叉树六、树与二叉树6.1 6.1 树的定义树的定义 树（树（TreeTree）：）：由由n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。 n=0n=0的树称为的树称为空树空树； n0n0的的非空非空树树T

2、T（D D，R R）有：）有： (1) (1)有且仅有一个结点有且仅有一个结点rootroot没有前驱结点，结点没有前驱结点，结点rootroot称作树的根节点。称作树的根节点。 (2) (2)除根结点外，其余结点有且仅有一个前驱结点除根结点外，其余结点有且仅有一个前驱结点，但可以有多个后继结点。，但可以有多个后继结点。六、树与二叉树六、树与二叉树树的递归定义树的递归定义由由n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。n=0n=0的树称为的树称为空树空树；对对n0n0的树的树T T有：有： （1 1）有一个特殊的结点称为根结点，根结）有一个特殊的结点称为根结点，根结点没有前

3、驱结点；点没有前驱结点； （2 2）当）当n1n1时，除根结点外其他结点被分成时，除根结点外其他结点被分成m m（m0m0）个互不相交的集合）个互不相交的集合T T1 1,T,T2 2,T,Tm m。其中。其中，每一个集合，每一个集合T Ti i(1im(1im）本身又是一棵称为）本身又是一棵称为根结点的子树的树。根结点的子树的树。六、树与二叉树六、树与二叉树（空树）（空树）（a）A（b）（c）ABCDEFGHIKLMJ六、树与二叉树六、树与二叉树树的基本术语树的基本术语 结点结点(Node):(Node):在树中通常把数据元素和在树中通常把数据元素和指向其指向其他节点的分支他节点的分支合起来

4、称作结点。合起来称作结点。 结点的度结点的度(Degree)(Degree)：结点所拥有的子树的个结点所拥有的子树的个数或者后继结点数称为该结点的度。数或者后继结点数称为该结点的度。 树的度：树的度：树中所有结点的度的最大值称为该树中所有结点的度的最大值称为该树的度。树的度。六、树与二叉树六、树与二叉树 叶结点叶结点(leaf)(leaf)：度为度为0 0的结点称为叶结点，叶的结点称为叶结点，叶结点也称作终端结点。结点也称作终端结点。 分支结点：分支结点：度不为度不为0 0的结点称为分支结点，分的结点称为分支结点，分支结点也称作非终端结点。（一棵树中除叶结支结点也称作非终端结点。（一棵树中除叶

5、结点外的所有结点都是分支结点）。点外的所有结点都是分支结点）。 孩子结点孩子结点(Child)(Child)：树中一个结点的子树的根树中一个结点的子树的根结点或者树中一个结点的后继结点称作这个结结点或者树中一个结点的后继结点称作这个结点的孩子结点，也称作后继结点。点的孩子结点，也称作后继结点。 双亲结点：双亲结点：若树中某结点有孩子结点，则该结若树中某结点有孩子结点，则该结点就称作他的孩子结点的双亲结点。点就称作他的孩子结点的双亲结点。六、树与二叉树六、树与二叉树 子孙结点：子孙结点：某一结点的所有孩子结点，以及某一结点的所有孩子结点，以及这些孩子结点的孩子结点称为该结点子孙结这些孩子结点的孩

6、子结点称为该结点子孙结点。点。 祖先结点：祖先结点：从根结点到树中某结点所经过的从根结点到树中某结点所经过的所有分支结点称为该结点的祖先结点。所有分支结点称为该结点的祖先结点。 兄弟结点兄弟结点(Sibling)(Sibling)：具有相同的双亲结点的具有相同的双亲结点的结点互相称之为兄弟结点。结点互相称之为兄弟结点。六、树与二叉树六、树与二叉树 结点的层次结点的层次(Level)(Level)：从根结点到树中某结点所经从根结点到树中某结点所经路径上的分支数称为该结点的层次，其中根结点为路径上的分支数称为该结点的层次，其中根结点为第一层。第一层。 树的深度（树的深度（Depth)Depth)：

7、树中所有结点的层次的最大值树中所有结点的层次的最大值称为该树的深度，空树的深度规定为称为该树的深度，空树的深度规定为0 0。 有序树：有序树：如果一棵树中任意一个结点的各个子树从如果一棵树中任意一个结点的各个子树从左到右都是有次序的。左到右都是有次序的。 森林森林(Forest)(Forest)：是是m(m0)m(m0)棵互不相交的树的集合。棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。对树中每个结点而言，其子树的集合即为森林。六、树与二叉树六、树与二叉树6.2 6.2 二叉树二叉树6.2.1 6.2.1 二叉树的定义二叉树的定义 二叉树二叉树(Binary Tree)(Bi

8、nary Tree)：树的度为树的度为2 2的有序树。的有序树。 二叉树是二叉树是n(n0)n(n0)个有限结点构成的集合。个有限结点构成的集合。n0n0的二叉树由一个根结点和两个互不相交的、分的二叉树由一个根结点和两个互不相交的、分别称作左子树和右子树的子二叉树构成。别称作左子树和右子树的子二叉树构成。六、树与二叉树六、树与二叉树 二叉树的五种结点形态：二叉树的五种结点形态：空结点、无左右子树空结点、无左右子树结点、只有左子树结点、只有右子树结点和左结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。右子树均存在的结点。空二叉树空二叉树只有一个根结点只有一个根结点左子树左子树根结点只

9、有左子树根结点只有左子树右子树右子树根结点只有右子树根结点只有右子树左子树左子树右子树右子树根结点同时有左右子树根结点同时有左右子树六、树与二叉树六、树与二叉树6.2.1 6.2.1 二叉树的性质二叉树的性质 性质性质3 3：对于一棵非空的二叉树，叶子结点数对于一棵非空的二叉树，叶子结点数n n0 0等等于度为于度为2 2的结点数的结点数n n2 2加加1 1，即，即n n0 0=n=n2 2+1;+1; 性质性质1 1：二叉树上第二叉树上第i i层上至多有层上至多有 （i1i1）12 i 性质性质2 2：深度为深度为h h的二叉树至多有的二叉树至多有 个结点。个结点。12 h六、树与二叉树六

10、、树与二叉树 满二叉树：满二叉树：在一棵二叉树中，如果所有分支结点都在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称作满二叉树。层上，这样的二叉树称作满二叉树。CDEFGHIJKLM NO1112 13 14 15六、树与二叉树六、树与二叉树 完全二叉树：完全二叉树：如果一棵树具有年如果一棵树具有年n n个结点的二叉树个结点的二叉树的结构与满二叉树的前的结构与满二叉树的前n n个结点的结构相同，这样个结点的结构相同，这样的二叉树称作完全二叉树。的二叉树称作完全二叉树。A152

11、34678910BCDEFGHIJ六、树与二叉树六、树与二叉树 性质性质4 4：具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度k k为为 。 1)(nlog2 性质性质5 5：对完全二叉树重编号为对完全二叉树重编号为i i的结点（的结点（1in1in，n1n1，n n为结点数）有：为结点数）有： 若若 ，即，即2in2in，则编号为，则编号为i i的结的结点为分支结点，否则为叶子结点。点为分支结点，否则为叶子结点。 若若i=0,i=0,是根，若是根，若i0i0，则它的双亲是，则它的双亲是 分支节点分支节点i i若存在左子女，则左子女是若存在左子女，则左子女是2 2* *i+1i

12、+1， 若存在右子女，则右子女是若存在右子女，则右子女是2 2* *i+2 i+2 2/ ni 2/1i六、树与二叉树六、树与二叉树6.2.2 6.2.2 二叉树的存储结构二叉树的存储结构1.1.顺序存储结构：顺序存储结构：首先给二叉树各结点编号（与等首先给二叉树各结点编号（与等深度的完全二叉树中位置上的结点编号相同），然深度的完全二叉树中位置上的结点编号相同），然后按编号的顺序将各结点的值存放的数组中。后按编号的顺序将各结点的值存放的数组中。 A B C D E H I J K F G 1 2 3 4 5 6 7 8 9 10 11 完全二叉树完全二叉树 A B C D E F G H IJ

13、 K123456789101112131415顺序存储结构顺序存储结构六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树ABCDEFG1234679ABCD EF G 1 2 3 4 5 6 7 8 9 MaxSize-1 位置位置data六、树与二叉树六、树与二叉树6.2.2 6.2.2 二叉树的存储结构二叉树的存储结构2. 2. 链链表表存储结构：存储结构：链表中每个结点包含三个域链表中每个结点包含三个域，一个数据域和两个指针域（分别指向对应结点，一个数据域和两个指针域（分别指向对应结点的左孩子和右孩子）。的左孩子和右孩子）。六、树与二叉树六、树与二叉树BACDEFGABCDEFGr

14、oot具有具有n个结点的二叉链表中，有个结点的二叉链表中，有n+1个空指针。个空指针。二叉树有一个表头指针，二叉树有一个表头指针，指向根节点指向根节点root。六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树6.3 6.3 二叉树的遍历二叉树的遍历树的遍历：树的遍历：从从根根结点出发，按照某种结点出发，按照某种次序访问次序访问树中所树中所有结点，使得每个结点被访问一次且仅被访问一次。有结点，使得每个结点被访问一次且仅被访问一次。 遍历的次序遍历的次序? ?树通常有前序遍历、中序遍历、后序遍历和层序树通常有前序遍历、中序遍历、后序遍历和层序遍历遍历4 4种方式。种方式。树结构（非线性结构

15、）树结构（非线性结构）线性结构。线性结构。遍历的实质遍历的实质? ?六、树与二叉树六、树与二叉树6.3.1 6.3.1 递归遍历二叉树递归遍历二叉树前序遍历前序遍历若二叉树为空，则空操作返回若二叉树为空，则空操作返回；否则：；否则：访问根结点；访问根结点；前序前序遍历遍历根根结点的左子树；结点的左子树；前序前序遍历遍历根根结点的右子树。结点的右子树。前序遍历序列：前序遍历序列：A B D G C E FA B D G C E FA AB BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树中序遍历中序遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回

16、；否则：否则：中序中序遍历遍历根根结点的左子树；结点的左子树；访问根结点；访问根结点；中序中序遍历遍历根根结点的右子树。结点的右子树。 中序遍历序列：中序遍历序列：D G B A E C FD G B A E C FA AB BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树后序遍历后序遍历若二叉树为空，则空操作返回；若二叉树为空，则空操作返回；否则：否则：后序后序遍历遍历根根结点的左子树；结点的左子树；后序后序遍历遍历根根结点的右子树。结点的右子树。访问根结点；访问根结点；后序遍历序列：后序遍历序列：G D B E F C AG D B E F C AA

17、 AB BC CD DE EF FG G六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树二叉树遍历操作练习二叉树遍历操作练习前序遍历结果：前序遍历结果：- + a * b - c d / e f中序遍历结果：中序遍历结果：a + b * c - d - e / f后序遍历结果：后序遍历结果：a b c d - * + e f / -六、树与二叉树六、树与二叉树若已知一棵二叉树的前序序列和中序序列，能否若已知一棵二叉树的前序序列和中序序列，能否唯一确定这棵二叉树呢？怎样确定？唯一确定这棵二叉树呢？怎样确定？ 例如：已知一棵二叉树的前序遍历序列和中序遍历例如：已知一棵二叉树的前序遍历序列和

18、中序遍历序列分别为序列分别为ABCDEFGHI ABCDEFGHI 和和BCAEDGHFIBCAEDGHFI，如何构造该二如何构造该二叉树呢叉树呢? ? 六、树与二叉树六、树与二叉树前序：前序：A B C D E F G H I中序：中序：B C A E D G H F I前序：前序：B C中序：中序：B C B C D EF GH IA前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI六、树与二叉树六、树与二叉树前序：前序：F G H I中序：中序：G H F I前序：前序： D E F G H I中序：中序： E D G H F IABCDEFGHI

19、ABCDEFIGH六、树与二叉树六、树与二叉树1. 1. 根据前序序列的第一个元素建立根结点；根据前序序列的第一个元素建立根结点；2. 2. 在中序序列中找到该元素，确定根结点的左右子在中序序列中找到该元素，确定根结点的左右子树的中序序列；树的中序序列；3. 3. 在前序序列中确定左右子树的前序序列；在前序序列中确定左右子树的前序序列；4. 4. 由左子树的前序序列和中序序列建立左子树；由左子树的前序序列和中序序列建立左子树；5. 5. 由右子树的前序序列和中序序列建立右子树。由右子树的前序序列和中序序列建立右子树。 课后习题课后习题1.1.（5 5）、）、（6 6）中序）中序cbdeagih

20、jfcbdeagihjf后序后序cebdijhgfa cebdijhgfa 已知一棵二叉树的前序序列和中序序列，构造该二叉已知一棵二叉树的前序序列和中序序列，构造该二叉树的过程如下：树的过程如下： 六、树与二叉树六、树与二叉树6.3.2 6.3.2 应用二叉树遍历的实例应用二叉树遍历的实例为了建立一棵二叉树，将二叉树中每个结点的空指为了建立一棵二叉树，将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值如针引出一个虚结点，其值为一特定值如“#”“#”，以标，以标识其为空，把这样处理后的二叉树称为原二叉树的识其为空，把这样处理后的二叉树称为原二叉树的扩展二叉树。扩展二叉树。 如何由一种遍历序

21、列建立一棵二叉树？如何由一种遍历序列建立一棵二叉树？遍历遍历是是二叉树二叉树各种操作的基础，可以在遍历的过程各种操作的基础，可以在遍历的过程中进行各种操作，例如建立一棵二叉树。中进行各种操作，例如建立一棵二叉树。六、树与二叉树六、树与二叉树扩展二叉树前序遍历序列扩展二叉树前序遍历序列:A B # D # # C # #DBAC#DBAC#建立二叉树建立二叉树六、树与二叉树六、树与二叉树BACDEFGABCDEFGroot扩展二叉树前序遍历序列扩展二叉树前序遍历序列:ABD#EG#CF#六、树与二叉树六、树与二叉树设二叉树中的结点均为一个字符。设二叉树中的结点均为一个字符。假设扩展二叉树的前序遍

22、历序列由键盘输入，假设扩展二叉树的前序遍历序列由键盘输入，rootroot为指向根结点的指针，二叉链表的建立过程是：为指向根结点的指针，二叉链表的建立过程是：首先输入根结点，若输入的是一个首先输入根结点，若输入的是一个“#”“#”字符，则表字符，则表明该二叉树为空树，即明该二叉树为空树，即root=NULLroot=NULL；否则输入的字符否则输入的字符应该赋给应该赋给root-data,root-data,，之后依次之后依次递归递归建立它的左子建立它的左子树和右子树树和右子树 。六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树计算二叉树的节点个数计算二叉树的节点个数六、树与二叉树六、

23、树与二叉树计算二叉树的高度计算二叉树的高度六、树与二叉树六、树与二叉树6.5 6.5 树与森林树与森林6.5.1 6.5.1 树的存储方式树的存储方式 2. 2.双亲双亲 表示法表示法 以一组连续的存储单元存以一组连续的存储单元存 放节点，节点包括放节点，节点包括datadata域域 和和parentparent域，后者存放域，后者存放 双亲节点的指针。双亲节点的指针。ABCDEFG0123456ABCDEFG-1000113dataparent六、树与二叉树六、树与二叉树6.5.1 6.5.1 树的存储方式树的存储方式3.3.左左 子女子女右右 兄弟表示法兄弟表示法 又称为二叉树表示法，每个

24、节点包括三个又称为二叉树表示法，每个节点包括三个域：域：datadata、firstChild(firstChild(存放第一个子女地址存放第一个子女地址) )nextSibling(nextSibling(存放下一个兄弟地址存放下一个兄弟地址) )六、树与二叉树六、树与二叉树 1. 1.兄弟加线兄弟加线. .树转换为二叉树的步骤树转换为二叉树的步骤ABCDEFG六、树与二叉树六、树与二叉树2.2.保留双亲与第一保留双亲与第一孩子连线孩子连线, ,删去与删去与其他孩子的连线其他孩子的连线. .ABCDEFG 1. 1.兄弟加线兄弟加线. .树转换为二叉树的步骤树转换为二叉树的步骤六、树与二叉树

25、六、树与二叉树3.3.顺时针转动顺时针转动, ,使使之层次分明之层次分明. .2.2.保留双亲与第一保留双亲与第一孩子连线孩子连线, ,删去与删去与其他孩子的连线其他孩子的连线. . 1. 1.兄弟加线兄弟加线. .GDABECF树转换为二叉树的步骤树转换为二叉树的步骤六、树与二叉树六、树与二叉树CBEDFGAABEFCDG前序遍历前序遍历AEBCFDGABEFCDG前序遍历前序遍历六、树与二叉树六、树与二叉树EFBCGDA后序遍历后序遍历EFBCGDA中序遍历中序遍历CBEDFGAAEBCFDG六、树与二叉树六、树与二叉树6.5.2 6.5.2 森林与二叉树的转换森林与二叉树的转换 将森林中

26、的每棵树转换成二叉树；将森林中的每棵树转换成二叉树； 从第二棵二叉树开始，依次把后一棵二叉树的从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。转换得到的二叉树。六、树与二叉树六、树与二叉树FEDCBAGH IKBAFEDCGH IKK IFEHABCGD六、树与二叉树六、树与二叉树 6.6 6.6 树的应用树的应用6.6.1 6.6.1 堆堆 堆是具有下列性质的堆是具有下列性质的完全二叉树完全二叉树：每个结点的

27、值都小于或：每个结点的值都小于或等于其左右孩子结点的值（称为等于其左右孩子结点的值（称为小根堆小根堆），或每个结点的值都），或每个结点的值都大于或等于其左右孩子结点的值（称为大于或等于其左右孩子结点的值（称为大根堆大根堆）。）。 18 18 26 263535 60 6048487373 74 53 42 35 2036 25 18 22六、树与二叉树六、树与二叉树堆的存储结构堆的存储结构1.1.顺序存储结构顺序存储结构将堆用顺序存储结构来存储，则堆对应一组序列。将堆用顺序存储结构来存储，则堆对应一组序列。18 26 35 73 48 60 0 1 2 3 4 5 6 7 8 9 18 18

28、26 263535 60 6048487373六、树与二叉树六、树与二叉树 性质：堆中性质：堆中0-n-10-n-1个结点编号中个结点编号中0 -10 -1的为分支节点，的为分支节点， -n-1-n-1的节点为叶子节点的节点为叶子节点若若 , ,是根，若是根，若i0i0，则它的双亲是，则它的双亲是 分支节点分支节点i i若存在左子女，则左子女是若存在左子女，则左子女是2 2* *i+1i+1， 若存在右子女，则右子女是若存在右子女，则右子女是2 2* *i+2 i+2 2/ ni 2/n2/n2/)1( i六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树 堆的建立、堆的建立、(2)(2

29、)清除堆、清除堆、(3)(3)检查一个堆是否为空检查一个堆是否为空 堆的运算堆的运算六、树与二叉树六、树与二叉树 2626 48 483535 60 6050507373ij六、树与二叉树六、树与二叉树 将新元素添加到堆尾，若新元素小于于双亲节将新元素添加到堆尾，若新元素小于于双亲节点，则需做调整：将双亲节点与新元素互换位置，点，则需做调整：将双亲节点与新元素互换位置，直至以新位置的双亲节点为根的子树仍为一个堆或直至以新位置的双亲节点为根的子树仍为一个堆或调整到堆顶为止；调整到堆顶为止； (4)(4)向堆中添加一个元素向堆中添加一个元素六、树与二叉树六、树与二叉树 18 18 26 26353

30、5 60 604848 73 73 1515 18 18 26 261515 60 60484873733535 1515 26 261818 60 60484873733535插入元素插入元素1515，元素调整过程，元素调整过程六、树与二叉树六、树与二叉树算法的时间复杂度取决于算法的时间复杂度取决于whilewhile循循环次数，等于新元素到堆顶逐层上环次数，等于新元素到堆顶逐层上移的次数，为移的次数，为O(log2n)O(log2n)六、树与二叉树六、树与二叉树 7070 55 551717 5 5 42 42 46 4613139494六、树与二叉树六、树与二叉树 4646 55 551

31、313 5 5 94 94 70 7017174242Currentsize/2-1六、树与二叉树六、树与二叉树 9494 70 701717 5 5 55 55 46 4613134242Currentsize/2-1六、树与二叉树六、树与二叉树 9494 70 701717 5 5 55 55 46 461313 4242六、树与二叉树六、树与二叉树 7070 55 551717 5 5 42 42 46 461313 9494六、树与二叉树六、树与二叉树 4646 5 51717 55 55 42 42 13 137070 9494六、树与二叉树六、树与二叉树六、树与二叉树六、树与二叉树

32、 6.6 6.6 树的应用树的应用6.6.2 6.6.2 哈夫曼树与编码哈夫曼树与编码1.1.相关术语相关术语路径长度：路径长度：树中从一个节点到另外一个节点间分支树中从一个节点到另外一个节点间分支构成了路径，路径中分支条数。构成了路径，路径中分支条数。 树的路径长度：树的路径长度：从树的根节点到树中各个节点的路从树的根节点到树中各个节点的路径长度之和。径长度之和。节点的带权路径长度：节点的带权路径长度：节点的路径长度与权的积节点的路径长度与权的积叶子结点的权值：叶子结点的权值：对叶子结点赋予的一个有意义的对叶子结点赋予的一个有意义的数值量。数值量。 六、树与二叉树六、树与二叉树2.2.哈夫曼

33、树：哈夫曼树：给定一组具有确定权值的给定一组具有确定权值的叶子叶子结点，带结点，带权路径长度最小的二叉树。权路径长度最小的二叉树。例：给定例：给定4 4个叶子结点，其权值分别为个叶子结点，其权值分别为11，3 3，4 4，66，可以构造出形状不同的多个二叉树。可以构造出形状不同的多个二叉树。 WPL=26 WPL=35 WPL=23 WPL=26 WPL=35 WPL=231 12 24 46 61 12 24 46 66 64 41 12 2六、树与二叉树六、树与二叉树哈夫曼树的特点：哈夫曼树的特点：1. 1. 权值越大的叶子结点越靠近根结点，而权值越小权值越大的叶子结点越靠近根结点，而权值

34、越小的叶子结点越远离根结点。的叶子结点越远离根结点。 2. 2. 只有度为只有度为0 0（叶子结点）和度为（叶子结点）和度为2 2（分支结点）的（分支结点）的结点，不存在度为结点，不存在度为1 1的结点的结点. . WPL=26 WPL=35 WPL=23 WPL=26 WPL=35 WPL=231 12 24 46 61 12 24 46 66 64 41 12 2六、树与二叉树六、树与二叉树哈夫曼算法基本思想：哈夫曼算法基本思想： 初始化初始化：由给定的：由给定的n n个权值个权值 w w1 1，w w2 2，w wn n 构造构造n n棵只有一个根结点的二叉树，从而得到一个二叉树棵只有一个根结点的二叉树，从而得到一个二叉树集合集合F F T T1 1，T T2 2，T Tn n ； 选取与合并选取与合并：在：在F F中选取根结点的权值中选取根结点的权值最小的两最小的两棵二叉树棵二叉树分别作为左、右子树构造一棵新的二叉树分别作为左、右子树构造一棵新的二叉树，这棵新二叉树的根结