《数据结构-C语言描述》第6章：树.ppt

第六章第六章 树和二叉树树和二叉树 树的概念与定义树的概念与定义 二二 叉叉 树树 二叉树的遍历与线索化二叉树的遍历与线索化 树和森林树和森林 哈夫曼树及其应用哈夫曼树及其应用 树树的计数的计数6.1树的概念与定义树的概念与定义树的定义：树的定义：树树(tree)(tree)是是n(n0)n(n0)个结点的有个结点的有限集限集T T，当，当n=0n=0时，称为空树；当时，称为空树；当n0n0时，满时，满足以下条件：足以下条件：（1 1）有且仅有一个结点被称为树根）有且仅有一个结点被称为树根（rootroot）结点；）结点；（2 2）当）当n1n1时，除根结点以外的其余时，除根结点以外的其余n-1n-1个个结点可以划分成结点可以划分成m(m0)m(m0)个互不相交的有限个互不相交的有限集集T1,T2,T1,T2,，TmTm，其中每一个集合本身又，其中每一个集合本身又是一棵树，称为根的子树是一棵树，称为根的子树(subtree)(subtree)。图6.1 结点结点(node)node)：表示树中的元素，包括数表示树中的元素，包括数据项及若干指向其子树的分支。据项及若干指向其子树的分支。结点的度结点的度(degree)degree)：结点拥有的子树的结点拥有的子树的数目。图数目。图6.16.1中结点中结点A A的度为的度为3 3。叶子叶子(leaf)leaf)：度为度为0 0的结点称为叶子结的结点称为叶子结点，也称为终端结点。图点，也称为终端结点。图6.16.1中，叶子中，叶子结点有：结点有：K K，L L，F F，G G，M M，I I，J J。分支结点分支结点：度不为度不为0 0的结点称为分支结的结点称为分支结点，也称为非终端结点。图点，也称为非终端结点。图6.16.1中，非中，非终端结点有：终端结点有：A A，B B，C C，D D等。等。孩子结点孩子结点(child)child)：结点的子树的根称结点的子树的根称为该结点的孩子结点。图为该结点的孩子结点。图6.16.1中，结点中，结点A A的孩子结点为的孩子结点为B B，C C，D D，结点结点B B的孩子结的孩子结点为点为E E，F F。双亲结点双亲结点(parents)parents)：孩子结点的上层孩子结点的上层结点称为该结点的双亲结点。图结点称为该结点的双亲结点。图6.16.1中，中，结点结点I I的双亲为的双亲为D D，结点结点L L的双亲为的双亲为E E。兄弟结点兄弟结点(sibling)sibling)：具有同一双亲结具有同一双亲结点的孩子结点之间互称为兄弟结点。图点的孩子结点之间互称为兄弟结点。图6.16.1中，结点中，结点B B，C C，D D互为兄弟，结点互为兄弟，结点K K，L L互为兄弟。互为兄弟。树的度树的度：树中最大的结点的度数即为树树中最大的结点的度数即为树的度。的度。图图6.16.1中的树的度为中的树的度为3 3。结点的层次结点的层次(level)level)：从根结点算起，从根结点算起，根为第一层，它的孩子为第二层根为第一层，它的孩子为第二层。若某结点在第若某结点在第l l层，则其孩子结点就在层，则其孩子结点就在第第l+1l+1层。图层。图6.16.1中，结点中，结点A A的层次为的层次为1 1，结点结点M M的层次为的层次为4 4。树的高度树的高度(depth)depth)：树中结点的最大层树中结点的最大层次数。图次数。图6.16.1中的树的高度为中的树的高度为4 4。森林森林(forest)forest)：m(mm(m0)0)棵互不相交的棵互不相交的树的集合。树的集合。有序树与无序树有序树与无序树：树中结点的各子树从左树中结点的各子树从左至右是有次序的（不能互换）则称该树为至右是有次序的（不能互换）则称该树为有序树有序树，否则称该树为，否则称该树为无序树。无序树。6.2 二叉树二叉树二叉树的定义：二叉树的定义：二叉树是由二叉树是由n(n0)n(n0)个个结点的有限集结点的有限集T T构成，此集合或者为空构成，此集合或者为空集，或者由一个根结点及两棵互不相交集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二的左右子树组成，并且左右子树都是二叉树。叉树。注意：注意：二叉树的子树有左右之分，因此二叉树的子树有左右之分，因此二叉树是一种有序树。二叉树是一种有序树。二叉树的性质：二叉树的性质：性质性质1 1 在二叉树的第在二叉树的第i i层上至多有层上至多有2 2i-1i-1个结点个结点(i i1)1)。性质性质2 2 深度为深度为k k的二叉树至多有的二叉树至多有2 2k k1 1个个结点（结点（k=1k=1）。）。性质性质3 3 对任意一棵二叉树对任意一棵二叉树BTBT，如果其如果其叶子结点数为叶子结点数为n n0 0，度为度为2 2的结点数为的结点数为n n2 2，则则n n0 0n n2 21 1。性质性质4 4 具有具有n n个结点的完全二叉树的深个结点的完全二叉树的深度为【度为【loglog2 2n n】1 1。（。（符号【符号【x x】表示不表示不大于大于x x的最大整数。）的最大整数。）二叉树的性质：二叉树的性质：性质性质5 5 对于具有对于具有n n个结点的完全二叉树，个结点的完全二叉树，如果对其结点按层次编号，则对任一结点如果对其结点按层次编号，则对任一结点i(1in)i(1in)，有：有：(1)(1)如如果果i=1i=1，则则结结点点i i是是二二叉叉树树的的根根，无无双双亲；如果亲；如果i1i1，则其双亲是【则其双亲是【i/2i/2】(2)(2)如如果果2 2inin，则则结结点点i i无无左左孩孩子子；如如果果2 2inin，则其左孩子是则其左孩子是2 2i i (3)(3)如如果果2 2i+1ni+1n，则则结结点点i i无无右右孩孩子子；如如果果2 2i+1ni+1n，则其右孩子是则其右孩子是2 2i+1i+1 满二叉树：满二叉树：一棵深度为一棵深度为k k且有且有2 2k k-1-1个结个结点的二叉树称为满二叉树。点的二叉树称为满二叉树。完全二叉树：完全二叉树：深度为深度为k k，有有n n个结点的二个结点的二叉树当且仅当其每一个结点都与深度为叉树当且仅当其每一个结点都与深度为k k的满二叉树中编号从的满二叉树中编号从1 1至至n n的结点一一对的结点一一对应时，称为完全二叉树。应时，称为完全二叉树。1231145891213671014151231145891267101234567123456二叉树的存储结构二叉树的存储结构 顺序存储结构顺序存储结构:为了能够反映出结点之间的逻为了能够反映出结点之间的逻为了能够反映出结点之间的逻为了能够反映出结点之间的逻辑关系，必须将它辑关系，必须将它辑关系，必须将它辑关系，必须将它“修补修补修补修补”成完全二叉树，对应该完成完全二叉树，对应该完成完全二叉树，对应该完成完全二叉树，对应该完全二叉树，可以开辟长度为全二叉树，可以开辟长度为全二叉树，可以开辟长度为全二叉树，可以开辟长度为1212的数组，对的数组，对的数组，对的数组，对1212个数据元个数据元个数据元个数据元素进行存储，原二叉树中空缺的结点在数组中的相应素进行存储，原二叉树中空缺的结点在数组中的相应素进行存储，原二叉树中空缺的结点在数组中的相应素进行存储，原二叉树中空缺的结点在数组中的相应单元必须置空单元必须置空单元必须置空单元必须置空 a a b b c c d d e e f f g g二叉树的存储结构二叉树的存储结构 链式存储结构链式存储结构:表示二叉树的链表中的结点应该表示二叉树的链表中的结点应该表示二叉树的链表中的结点应该表示二叉树的链表中的结点应该包含包含包含包含3 3 3 3个域：数据域和指向左、右子树的指针域，二叉树个域：数据域和指向左、右子树的指针域，二叉树个域：数据域和指向左、右子树的指针域，二叉树个域：数据域和指向左、右子树的指针域，二叉树的这种存储结构被称为二叉链表。的这种存储结构被称为二叉链表。的这种存储结构被称为二叉链表。的这种存储结构被称为二叉链表。LchildLchilddatadatarchildrchild在n个结点的二叉链表中，有n+1个空指针域6.3 6.3 二叉树的遍历与线索化二叉树的遍历与线索化 二叉树的遍历：二叉树的遍历：是按某条搜索路径访问树是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。问一次，而且仅被访问一次。先根遍历二叉树先根遍历二叉树 （1 1）访问根结点；）访问根结点；（2 2）先根遍历左子树；）先根遍历左子树；（3 3）先根遍历右子树。）先根遍历右子树。中根遍历二叉树中根遍历二叉树（1 1）中根遍历左子树；）中根遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中根遍历右子树。）中根遍历右子树。后根遍历二叉树后根遍历二叉树 （1 1）后根遍历左子树；）后根遍历左子树；（2 2）后根遍历右子树；）后根遍历右子树；（3 3）访问根结点。）访问根结点。先根遍历先根遍历先根遍历先根遍历:-+a*bcd/ef:-+a*bcd/ef:-+a*bcd/ef:-+a*bcd/ef中根遍历中根遍历中根遍历中根遍历:a+b*cde/f:a+b*cde/f:a+b*cde/f:a+b*cde/f后根遍历后根遍历后根遍历后根遍历:abcd-*+ef/-:abcd-*+ef/-:abcd-*+ef/-:abcd-*+ef/-typedef struct Node datatype data;struct Node*Lchild;struct Node*Rchild;BTnode,*Btree;先根遍历算法void preorder(Btree root)if(root!=NULL)Visit(root-data);preorder(root-Lchild);preorder(root-Rchild);中根遍历算法void InOrder(Btree root)if(root!=NULL)InOrder(root-Lchild);Visit(root-data);InOrder(root-Rchild);后根遍历算法void PostOrder(Btree root)if(root!=NULL)PostOrder(root-Lchild);PostOrder(root-Rchild);Visit(root-data);线索二叉树：线索二叉树：利用二插链表剩余的利用二插链表剩余的n+1n+1个空个空指针域来存放遍历过程中结点的前驱和后继指针域来存放遍历过程中结点的前驱和后继的指针，这种附加的指针称为的指针，这种附加的指针称为“线索线索”，加，加上了线索的二叉链表称为线索链表，相应的上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。二叉树称为线索二叉树。为了区分结点的指针域是指向其孩子的指为了区分结点的指针域是指向其孩子的指针，还是指向其前驱或后继的线索，可在二针，还是指向其前驱或后继的线索，可在二叉链表的结点中叉链表的结点中,再增设再增设2 2个标志域。个标志域。LchildLchildLchildLchildLtagLtagLtagLtagDataDataDataDataRtagRtagRtagRtagRchildRchildRchildRchild 0 Lchild 0 Lchild域指示结点的左孩子域指示结点的左孩子Ltag=Ltag=1 Lchild 1 Lchild域指示结点的遍历前驱域指示结点的遍历前驱 0 0 RchildRchild域域指指示示结结点点的的右右孩孩子子Rtag=Rtag=1 Rchild 1 Rchild域指示结点的遍历后继域指示结点的遍历后继中序线索二叉树中序线索二叉树 基于遍历的应用与线索二叉树的应用基于遍历的应用与线索二叉树的应用 二叉树的遍历是对二叉树进行各种运算二叉树的遍历是对二叉树进行各种运算的一个重要基础，对访问（程序中的的一个重要基础，对访问（程序中的visitvisit函函数）结点可理解为各种对二叉树中结点进行数）结点可理解为各种对二叉树中结点进行操作。因此，只要将二叉树三种遍历算法中操作。因此，只要将二叉树三种遍历算法中的的visitvisit函数具体化，就产生了基于二叉树的函数具体化，就产生了基于二叉树的不同应用。不同应用。输出二叉树中的结点输出二叉树中的结点 Void paintnode(Btree root)if(root!=NULL)printf(root-data);paintnode(root-Lchild);paintnode(root-Rchild);输出二叉树中的叶子结点输出二叉树中的叶子结点Void paintleaf(Btree root)if(root!=NULL)if(root-Lchild=NULL&root-Rchild=NULL)printf(root-data);paintleaf(root-Lchild);paintleaf(root-Rchild);统计叶子结点数目统计叶子结点数目Void leafcount(Btree root)if(root!=NULL)leafcount(root-Lchild);leafcount(root-Rchild);if(root-Lchild=NULL&root-Rchild=NULL)count+;提示：提示：提示：提示：countcountcountcount为全局变量，在主函数中定义。为全局变量，在主函数中定义。为全局变量，在主函数中定义。为全局变量，在主函数中定义。建立二叉树建立二叉树图图图图中中中中二二二二叉叉叉叉树树树树的的的的先先先先根根根根遍遍遍遍历历历历序序序序列列列列为为为为：ABDGCEHFABDGCEHFABDGCEHFABDGCEHF，而而而而考考考考虑虑虑虑空空空空子子子子树树树树后后后后的的的的先先先先根根根根遍遍遍遍历历历历序序序序列列列列应应应应为为为为：ABDABDABDABDG G G GCECECECEHFHFHFHF，其中其中其中其中“”代表空子树。代表空子树。代表空子树。代表空子树。如如如如果果果果已已已已知知知知二二二二叉叉叉叉树树树树的的的的考考考考虑虑虑虑了了了了空空空空子子子子树树树树后后后后的的的的遍遍遍遍历历历历序序序序列列列列，那那那那么么么么建建建建立立立立这这这这棵棵棵棵二二二二叉叉叉叉树树树树的的的的算算算算法法法法如如如如下下下下(假假假假定定定定datatypedatatypedatatypedatatype类类类类型型型型为为为为char)char)char)char)：Void CreateBtree(Btree*bt)char ch;ch=getchar();if(ch=.)*bt=NULL;else*bt=(Btree)malloc(sizeof(BTnode);(*bt)-data=ch;CreateBiTree(&(*bt)-Lchild);CreateBiTree(&(*bt)-Rchild);求二叉树的高度求二叉树的高度采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：（1 1 1 1）若二叉树为空，则高度为）若二叉树为空，则高度为）若二叉树为空，则高度为）若二叉树为空，则高度为0 0 0 0；（2 2 2 2）若二叉树非空，其高度应为其左右子树高度的最）若二叉树非空，其高度应为其左右子树高度的最）若二叉树非空，其高度应为其左右子树高度的最）若二叉树非空，其高度应为其左右子树高度的最大值加大值加大值加大值加1 1 1 1。int TreeDepth(Btree bt)int hl,hr,max;if(bt!=NULL)hl=TreeDepth(bt-Lchild);hr=TreeDepth(bt-Rchild);max=(hl，hr);return(max+1);else return(0);在中根遍历的线索树中查找前驱结点在中根遍历的线索树中查找前驱结点 对于二叉树中任意结点对于二叉树中任意结点对于二叉树中任意结点对于二叉树中任意结点p p p p，要找其前驱结点，要找其前驱结点，要找其前驱结点，要找其前驱结点,当当当当p-Ltag=1p-Ltag=1p-Ltag=1p-Ltag=1时，时，时，时，p-Lchildp-Lchildp-Lchildp-Lchild即为即为即为即为p p p p的前驱结点；当的前驱结点；当的前驱结点；当的前驱结点；当p-Ltag=0p-Ltag=0p-Ltag=0p-Ltag=0时，说明时，说明时，说明时，说明p p p p有左子树，此时有左子树，此时有左子树，此时有左子树，此时p p p p的中根遍历下的前驱结点即为其左子树的中根遍历下的前驱结点即为其左子树的中根遍历下的前驱结点即为其左子树的中根遍历下的前驱结点即为其左子树右链下的最后一个结点。右链下的最后一个结点。右链下的最后一个结点。右链下的最后一个结点。Void Previous(ThreadTnode*p,ThreadTnode*pre)ThreadTnode*q;if(p-Ltag=1)pre=p-Lchild;else for(q=p-Lchild;q-Rtag=0;q=q-Rchild);pre=q;在中根遍历的线索树中查找后继结点在中根遍历的线索树中查找后继结点 二叉树中任意结点二叉树中任意结点二叉树中任意结点二叉树中任意结点p p p p，若要找其后继结点，当，若要找其后继结点，当，若要找其后继结点，当，若要找其后继结点，当p-Rtag=1p-Rtag=1p-Rtag=1p-Rtag=1时，时，时，时，p-Rchildp-Rchildp-Rchildp-Rchild即为即为即为即为p p p p的后继结点；当的后继结点；当的后继结点；当的后继结点；当p-Rtag=0p-Rtag=0p-Rtag=0p-Rtag=0时，说明时，说明时，说明时，说明p p p p有右有右有右有右子树，此时子树，此时子树，此时子树，此时p p p p的中根遍历下的后继结点即为其右子树左链的中根遍历下的后继结点即为其右子树左链的中根遍历下的后继结点即为其右子树左链的中根遍历下的后继结点即为其右子树左链下的最后一个结点。下的最后一个结点。下的最后一个结点。下的最后一个结点。Void Succedent(ThreadTnode*p,ThreadTnode*succ)ThreadTnode*q;if(p-Rtag=1)succ=p-RChild;else for(q=p-RChild;q-Ltag=0;q=q-LChild);succ=q;6.4 6.4 树和森林树和森林树的存储结构树的存储结构 双亲（链表）表示法双亲（链表）表示法双亲（链表）表示法双亲（链表）表示法 vv 用一组连续的存储空间（数组）来存储树中的结点，每个数用一组连续的存储空间（数组）来存储树中的结点，每个数用一组连续的存储空间（数组）来存储树中的结点，每个数用一组连续的存储空间（数组）来存储树中的结点，每个数组元素中不但包含结点本身的信息，还保存该结点双亲结点在组元素中不但包含结点本身的信息，还保存该结点双亲结点在组元素中不但包含结点本身的信息，还保存该结点双亲结点在组元素中不但包含结点本身的信息，还保存该结点双亲结点在数组中的下标号。数组中数组中的下标号。数组中数组中的下标号。数组中数组中的下标号。数组中每个结点含两个域：每个结点含两个域：每个结点含两个域：每个结点含两个域：数据域：存放结点本身信息数据域：存放结点本身信息数据域：存放结点本身信息数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置双亲域：指示本结点的双亲结点在数组中位置双亲域：指示本结点的双亲结点在数组中位置双亲域：指示本结点的双亲结点在数组中位置在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：#define Maxsize 50typedef struct NodeDataType data;int parent;Tnode;Tnode PtreeMaxsize;abcdefhgiacdefghib112235551601234578dataparent如何找孩子结点孩子链表表示法孩子链表表示法孩子链表表示法孩子链表表示法把每个结点的孩子结点排列起来，构成一个单链表，该单把每个结点的孩子结点排列起来，构成一个单链表，该单把每个结点的孩子结点排列起来，构成一个单链表，该单把每个结点的孩子结点排列起来，构成一个单链表，该单链表就是本结点的孩子链表。具有链表就是本结点的孩子链表。具有链表就是本结点的孩子链表。具有链表就是本结点的孩子链表。具有n n n n个结点的树就形成了个结点的树就形成了个结点的树就形成了个结点的树就形成了n n n n个孩子链表个孩子链表个孩子链表个孩子链表 v 孩子结点#define Maxsize 50typedef struct ChildNodeint Child;struct ChildNode*next;ChildNode;v表头结点typedef structDataType data;ChildNode*ChildHead;DataNode;v 孩子链表 DataNode CtreeMaxsize;孩子兄弟链表表示法孩子兄弟链表表示法孩子兄弟链表表示法孩子兄弟链表表示法 又称为二叉链表表示法，即以二叉链表作为树的存储结构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）。（右兄弟）。（右兄弟）。（右兄弟）。FirstChildFirstChilddatadataNextsiblingNextsiblingtypedef struct CSNode DataType data;Struct CSNode*FirstChild,*Nextsibling;*CSTree;对应对应结论：树的结论：树的结论：树的结论：树的孩子兄弟链表表示法与对应二叉树的二插链表表示法相孩子兄弟链表表示法与对应二叉树的二插链表表示法相孩子兄弟链表表示法与对应二叉树的二插链表表示法相孩子兄弟链表表示法与对应二叉树的二插链表表示法相同。因此，上图中的树与二叉树之间存在相互转换的关系。同。因此，上图中的树与二叉树之间存在相互转换的关系。同。因此，上图中的树与二叉树之间存在相互转换的关系。同。因此，上图中的树与二叉树之间存在相互转换的关系。ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空 树转换为二叉树树转换为二叉树树转换为二叉树树转换为二叉树 v 加线：在树中所有相邻的兄弟之间加一连线；加线：在树中所有相邻的兄弟之间加一连线；v 抹线：对树中每个结点，除了其左孩子外抹去该结点与其余抹线：对树中每个结点，除了其左孩子外抹去该结点与其余孩子之间的连线。孩子之间的连线。v 整理：以树的根结点为轴心，将整树顺时针转整理：以树的根结点为轴心，将整树顺时针转4545。森林转换成二叉树森林转换成二叉树森林转换成二叉树森林转换成二叉树vv 将各棵树分别转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树vv 将每棵树的根结点用线相连将每棵树的根结点用线相连将每棵树的根结点用线相连将每棵树的根结点用线相连vv 以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ 二叉二叉二叉二叉树转换成树树转换成树树转换成树树转换成树vv加线：若加线：若加线：若加线：若p p p p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p p p p的右孩子，右的右孩子，右的右孩子，右的右孩子，右孩子的右孩子，孩子的右孩子，孩子的右孩子，孩子的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p p p p的的的的双亲用线连起来双亲用线连起来双亲用线连起来双亲用线连起来vv抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线vv调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI 二叉树转换成森林二叉树转换成森林二叉树转换成森林二叉树转换成森林vv 抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树vv 还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ树和森林的遍历树和森林的遍历 树的遍历树的遍历树的遍历树的遍历 vv 先根遍历先根遍历先根遍历先根遍历 若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：a.a.a.a.访问根结点。访问根结点。访问根结点。访问根结点。b.b.b.b.从左到右，依次先根遍历根结点的每一棵子树。从左到右，依次先根遍历根结点的每一棵子树。从左到右，依次先根遍历根结点的每一棵子树。从左到右，依次先根遍历根结点的每一棵子树。vv 后根遍历后根遍历后根遍历后根遍历 若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：a.a.a.a.从左到右，依次后根遍历根结点的每一棵子树。从左到右，依次后根遍历根结点的每一棵子树。从左到右，依次后根遍历根结点的每一棵子树。从左到右，依次后根遍历根结点的每一棵子树。b.b.b.b.访问根结点。访问根结点。访问根结点。访问根结点。vv 按层次遍历按层次遍历按层次遍历按层次遍历 若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：若树非空，则遍历方法为：先访问第一层上的结点，然后依次遍历第二层，先访问第一层上的结点，然后依次遍历第二层，先访问第一层上的结点，然后依次遍历第二层，先访问第一层上的结点，然后依次遍历第二层，第第第第n n n n 层的结层的结层的结层的结点。点。点。点。ABCDEFGHIJKLMNO先根遍历：后根遍历：层次遍历：ABE F I GCDHJ KL NOME I F G B C J K N O L M H D AAB C DE F GH I J KL MNO森林的遍历森林的遍历森林的遍历森林的遍历vv 先根遍历先根遍历先根遍历先根遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：1.1.1.1.a.a.a.a.访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。b.b.b.b.先根遍历第一棵树的根结点的子树森林。先根遍历第一棵树的根结点的子树森林。先根遍历第一棵树的根结点的子树森林。先根遍历第一棵树的根结点的子树森林。c.c.c.c.先根遍历除去第一棵树之后剩余的树构成的森林。先根遍历除去第一棵树之后剩余的树构成的森林。先根遍历除去第一棵树之后剩余的树构成的森林。先根遍历除去第一棵树之后剩余的树构成的森林。vv中根遍历中根遍历中根遍历中根遍历 若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：a.a.a.a.中根遍历森林中第一棵树的根结点的子树森林。中根遍历森林中第一棵树的根结点的子树森林。中根遍历森林中第一棵树的根结点的子树森林。中根遍历森林中第一棵树的根结点的子树森林。b.b.b.b.访问第一棵树的根结点。访问第一棵树的根结点。访问第一棵树的根结点。访问第一棵树的根结点。c.c.c.c.中根遍历除去第一棵树之后剩余的树构成的森林。中根遍历除去第一棵树之后剩余的树构成的森林。中根遍历除去第一棵树之后剩余的树构成的森林。中根遍历除去第一棵树之后剩余的树构成的森林。vv后根遍历后根遍历后根遍历后根遍历 若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：若森林非空，则遍历方法为：a.a.a.a.后根遍历森林中第一棵树的根结点的子树森林。后根遍历森林中第一棵树的根结点的子树森林。后根遍历森林中第一棵树的根结点的子树森林。后根遍历森林中第一棵树的根结点的子树森林。b.b.b.b.后根遍历除去第一棵树之后剩余的树构成的森林。后根遍历除去第一棵树之后剩余的树构成的森林。后根遍历除去第一棵树之后剩余的树构成的森林。后根遍历除去第一棵树之后剩余的树构成的森林。c.c.c.c.访问第一棵树的根结点。访问第一棵树的根结点。访问第一棵树的根结点。访问第一棵树的根结点。先根遍历：A B C D E F G H I J中根遍历：B C D A F E H J I G后根遍历：D C B F J I H G E A6.5 6.5 哈夫曼树及其应用哈夫曼树及其应用 与哈夫曼树相关的基本概念与哈夫曼树相关的基本概念与哈夫曼树相关的基本概念与哈夫曼树相关的基本概念 vv 路径和路径长度路径和路径长度路径和路径长度路径和路径长度 路径：从一个结点到另一个结点之间的分支序列。路径：从一个结点到另一个结点之间的分支序列。路径：从一个结点到另一个结点之间的分支序列。路径：从一个结点到另一个结点之间的分支序列。路径长度：是指从一个结点到另一个结点所经过的分支数目。路径长度：是指从一个结点到另一个结点所经过的分支数目。路径长度：是指从一个结点到另一个结点所经过的分支数目。路径长度：是指从一个结点到另一个结点所经过的分支数目。vv 结点的权和带权路径长度结点的权和带权路径长度结点的权和带权路径长度结点的权和带权路径长度 结点的权：在实际的应用中，人们常常给树的每个结点赋予结点的权：在实际的应用中，人们常常给树的每个结点赋予结点的权：在实际的应用中，人们常常给树的每个结点赋予结点的权：在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的数值，我们称该数值为这个结点的权。一个具有某种实际意义的数值，我们称该数值为这个结点的权。一个具有某种实际意义的数值，我们称该数值为这个结点的权。一个具有某种实际意义的数值，我们称该数值为这个结点的权。结点的带权路径长度：从树根到某一结点的路径长度与该结结点的带权路径长度：从树根到某一结点的路径长度与该结结点的带权路径长度：从树根到某一结点的路径长度与该结结点的带权路径长度：从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。点的权的乘积，叫做该结点的带权路径长度。点的权的乘积，叫做该结点的带权路径长度。点的权的乘积，叫做该结点的带权路径长度。vv 树的带权路径长度树的带权路径长度树的带权路径长度树的带权路径长度 树的带权路径长度是指树中所有叶子结点的带权路径长度树的带权路径长度是指树中所有叶子结点的带权路径长度树的带权路径长度是指树中所有叶子结点的带权路径长度树的带权路径长度是指树中所有叶子结点的带权路径长度之和。之和。之和。之和。vv 树的带权路径长度树的带权路径长度树的带权路径长度树的带权路径长度 树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径长度之和。长度之和。长度之和。长度之和。哈夫曼树：是由哈夫曼树：是由哈夫曼树：是由哈夫曼树：是由n n n n个带权叶子结点构成的所有二叉树中带权路径个带权叶子结点构成的所有二叉树中带权路径个带权叶子结点构成的所有二叉树中带权路径个带权叶子结点构成的所有二叉树中带权路径长度长度长度长度WPLWPLWPLWPL最小的二叉树。哈夫曼树又叫最佳判定树。最小的二叉树。哈夫曼树又叫最佳判定树。最小的二叉树。哈夫曼树又叫最佳判定树。最小的二叉树。哈夫曼树又叫最佳判定树。vv 哈夫曼树哈夫曼树哈夫曼树哈夫曼树例：有例：有例：有例：有4 4 4 4个结点，权值分别为个结点，权值分别为个结点，权值分别为个结点，权值分别为7 7 7 7，5 5 5 5，2 2 2 2，4 4 4 4，构造有，构造有，构造有，构造有4 4 4 4个叶子结点的二叉树个叶子结点的二叉树个叶子结点的二叉树个叶子结点的二叉树abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35构造构造构造构造HuffmanHuffmanHuffmanHuffman树的方法树的方法树的方法树的方法HuffmanHuffmanHuffmanHuffman算法算法算法算法v 构造构造构造构造HuffmanHuffmanHuffmanHuffman树步骤树步骤树步骤树步骤 根据给定的根据给定的根据给定的根据给定的n n n n个权值个权值个权值个权值 w1,w2,w1,w2,w1,w2,w1,w2,wnwnwnwn ，构造构造构造构造n n n n棵只有根结棵只有根结棵只有根结棵只有根结点的二叉树，令起权值为点的二叉树，令起权值为点的二叉树，令起权值为点的二叉树，令起权值为wjwjwjwj 在森林中选取两棵根结点权值最小的树作左右子树，构在森林中选取两棵根结点权值最小的树作左右子树，构在森林中选取两棵根结点权值最小的树作左右子树，构在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子造一棵新的二叉树，置新二叉树根结点权值为其左右子造一棵新的二叉树，置新二叉树根结点权值为其左右子造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和树根结点权值之和树根结点权值之和树根结点权值之和 在森林中删除这两棵树，同时将新得到的二叉树加入森在森林中删除这两棵树，同时将新得到的二叉树加入森在森林中删除这两棵树，同时将新得到的二叉树加入森在森林中删除这两棵树，同时将新得到的二叉树加入森林中林中林中林中 重复上述两步，直到只含一棵树为止，