《数据结构-C语言版：DS06-树》由会员分享，可在线阅读，更多相关《数据结构-C语言版：DS06-树（100页珍藏版）》请在金锄头文库上搜索。
1、第 章 树 和 二 叉 树 第六章第六章 树和二叉树树和二叉树 树的概念与定义树的概念与定义 二二 叉叉 树树 二叉树的遍历与线索化二叉树的遍历与线索化 树和森林树和森林 哈夫曼树及其应用哈夫曼树及其应用 树的计数树的计数第 章 树 和 二 叉 树 6.1 6.1 树的概念与定义树的概念与定义树的定义：树的定义：树的定义：树的定义：树树树树(tree)(tree)(tree)(tree)是是是是n(n0)n(n0)n(n0)n(n0)个结点的有个结点的有个结点的有个结点的有限集限集限集限集T T T T，当，当，当，当n=0n=0n=0n=0时，称为空树；当时，称为空树；当时，称为空树；当时，
2、称为空树；当n0n0n0n0时，满时，满时，满时，满足以下条件：足以下条件：足以下条件：足以下条件： （1 1 1 1）有且仅有一个结点被称为树根）有且仅有一个结点被称为树根）有且仅有一个结点被称为树根）有且仅有一个结点被称为树根（rootrootrootroot）结点；）结点；）结点；）结点；（2 2 2 2）当）当）当）当n1n1n1n1时，除根结点以外的其余时，除根结点以外的其余时，除根结点以外的其余时，除根结点以外的其余n-1n-1n-1n-1个个个个结点可以划分成结点可以划分成结点可以划分成结点可以划分成m(m0)m(m0)m(m0)m(m0)个互不相交的有限集个互不相交的有限集个互
3、不相交的有限集个互不相交的有限集T T T T1 1 1 1,T,T,T,T2 2 2 2, , , ,，T T T Tm m m m，其中每一个集合本身又是一，其中每一个集合本身又是一，其中每一个集合本身又是一，其中每一个集合本身又是一棵树，称为根的子树棵树，称为根的子树棵树，称为根的子树棵树，称为根的子树(subtree)(subtree)(subtree)(subtree)。 第 章 树 和 二 叉 树 图6.1 第 章 树 和 二 叉 树 结点结点结点结点(node)(node)(node)(node)：表示树中的元素，包括数据项及表示树中的元素，包括数据项及表示树中的元素，包括数据项
4、及表示树中的元素，包括数据项及若干指向其子树的分支。若干指向其子树的分支。若干指向其子树的分支。若干指向其子树的分支。 结点的度结点的度结点的度结点的度(degree)(degree)(degree)(degree)：结点拥有的子树的数目。结点拥有的子树的数目。结点拥有的子树的数目。结点拥有的子树的数目。图图图图6.16.16.16.1中结点中结点中结点中结点A A A A的度为的度为的度为的度为3 3 3 3。 叶子叶子叶子叶子(leaf)(leaf)(leaf)(leaf)：度为度为度为度为0 0 0 0的结点称为叶子结点，也的结点称为叶子结点，也的结点称为叶子结点，也的结点称为叶子结点，
5、也称为终端结点。图称为终端结点。图称为终端结点。图称为终端结点。图6.16.16.16.1中，叶子结点有：中，叶子结点有：中，叶子结点有：中，叶子结点有：K K K K，L L L L，F F F F，G G G G，M M M M，I I I I，J J J J。 分支结点：分支结点：分支结点：分支结点：度不为度不为度不为度不为0 0 0 0的结点称为分支结点，也的结点称为分支结点，也的结点称为分支结点，也的结点称为分支结点，也称为非终端结点。图称为非终端结点。图称为非终端结点。图称为非终端结点。图6.16.16.16.1中，非终端结点有：中，非终端结点有：中，非终端结点有：中，非终端结点有
6、：A A A A，B B B B，C C C C，D D D D等。等。等。等。 第 章 树 和 二 叉 树 孩子结点孩子结点孩子结点孩子结点(child)(child)(child)(child)：结点的子树的根称为该结结点的子树的根称为该结结点的子树的根称为该结结点的子树的根称为该结点的孩子结点。图点的孩子结点。图点的孩子结点。图点的孩子结点。图6.16.16.16.1中，结点中，结点中，结点中，结点A A A A的孩子结点的孩子结点的孩子结点的孩子结点为为为为B B B B，C C C C，D D D D，结点，结点，结点，结点B B B B的孩子结点为的孩子结点为的孩子结点为的孩子结点
7、为E E E E，F F F F。 双亲结点双亲结点双亲结点双亲结点(parents)(parents)(parents)(parents)：孩子结点的上层结点称孩子结点的上层结点称孩子结点的上层结点称孩子结点的上层结点称为该结点的双亲结点。图为该结点的双亲结点。图为该结点的双亲结点。图为该结点的双亲结点。图6.16.16.16.1中，结点中，结点中，结点中，结点I I I I的双的双的双的双亲为亲为亲为亲为D D D D，结点，结点，结点，结点L L L L的双亲为的双亲为的双亲为的双亲为E E E E。 兄弟结点兄弟结点兄弟结点兄弟结点(sibling)(sibling)(sibling)
8、(sibling)：具有同一双亲结点的孩具有同一双亲结点的孩具有同一双亲结点的孩具有同一双亲结点的孩子结点之间互称为兄弟结点。图子结点之间互称为兄弟结点。图子结点之间互称为兄弟结点。图子结点之间互称为兄弟结点。图6.16.16.16.1中，结点中，结点中，结点中，结点B B B B，C C C C，D D D D互为兄弟，结点互为兄弟，结点互为兄弟，结点互为兄弟，结点K K K K，L L L L互为兄弟。互为兄弟。互为兄弟。互为兄弟。 第 章 树 和 二 叉 树 树的度：树的度：树的度：树的度：树中最大的结点的度数即为树的度。树中最大的结点的度数即为树的度。树中最大的结点的度数即为树的度。树
9、中最大的结点的度数即为树的度。图图图图6.16.16.16.1中的树的度为中的树的度为中的树的度为中的树的度为3 3 3 3。结点的层次结点的层次结点的层次结点的层次(level)(level)(level)(level)：从根结点算起，根为第从根结点算起，根为第从根结点算起，根为第从根结点算起，根为第一层，它的孩子为第二层一层，它的孩子为第二层一层，它的孩子为第二层一层，它的孩子为第二层。若某结点在。若某结点在。若某结点在。若某结点在第第第第l l l l层，则其孩子结点就在第层，则其孩子结点就在第层，则其孩子结点就在第层，则其孩子结点就在第l+1l+1l+1l+1层。图层。图层。图层。图6
10、.16.16.16.1中，中，中，中，结点结点结点结点A A A A的层次为的层次为的层次为的层次为1 1 1 1，结点，结点，结点，结点M M M M的层次为的层次为的层次为的层次为4 4 4 4。树的高度树的高度树的高度树的高度(depth)(depth)(depth)(depth)：树中结点的最大层次数。树中结点的最大层次数。树中结点的最大层次数。树中结点的最大层次数。图图图图6.16.16.16.1中的树的高度为中的树的高度为中的树的高度为中的树的高度为4 4 4 4。 森林森林森林森林(forest)(forest)(forest)(forest)：m(m0)m(m0)m(m0)m(
11、m0)棵互不相交的树的集棵互不相交的树的集棵互不相交的树的集棵互不相交的树的集合。合。合。合。第 章 树 和 二 叉 树 树中结点的各子树从左至右是有树中结点的各子树从左至右是有次序的（不能互换）则称该树为次序的（不能互换）则称该树为有序树，有序树，否则称该树为否则称该树为无序树。无序树。有序树与无序树：有序树与无序树：第 章 树 和 二 叉 树 6.2 6.2 二叉树二叉树二叉树的定义：二叉树的定义：二叉树的定义：二叉树的定义：二叉树是由二叉树是由二叉树是由二叉树是由n(n0)n(n0)n(n0)n(n0)个结点个结点个结点个结点的有限集的有限集的有限集的有限集T T T T构成，此集合或者
12、为空集，或者构成，此集合或者为空集，或者构成，此集合或者为空集，或者构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组由一个根结点及两棵互不相交的左右子树组由一个根结点及两棵互不相交的左右子树组由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。成，并且左右子树都是二叉树。成，并且左右子树都是二叉树。成，并且左右子树都是二叉树。注意：注意：注意：注意：二叉树的子树有左右之分，因此二叉二叉树的子树有左右之分，因此二叉二叉树的子树有左右之分，因此二叉二叉树的子树有左右之分，因此二叉树是一种有序树。树是一种有序树。树是一种有序树。树是一种有序树。 第 章 树 和 二 叉
13、 树 二叉树的性质二叉树的性质：性质性质性质性质1 1 1 1 在二叉树的第在二叉树的第在二叉树的第在二叉树的第i i i i层上至多有层上至多有层上至多有层上至多有2 2 2 2i-1i-1i-1i-1个结点个结点个结点个结点(i1)(i1)(i1)(i1)。用归纳法证明此性质：用归纳法证明此性质：当当i=1时，只有一个根结点，显然时，只有一个根结点，显然2i-1=21-1=20=1；现现在在假假定定对对所所有有的的j，1j=1k=1k=1k=1）。）。）。）。 证证明明：因因为为深深度度为为k的的二二叉叉树树,其其结结点点总总数数的的最最大大值值是是将将二二叉叉树树每每层层上上结结点点数数
14、的的最最大大值值相相加加，所以深度为所以深度为k的二叉树的结点总数至多为：的二叉树的结点总数至多为：第第i层的最大结点数层的最大结点数=2 2 2 2i i i i1 1 1 1 = = = = 2k-1。ki=1ki=1第 章 树 和 二 叉 树 性质性质性质性质3 3 3 3 对任意一棵二叉树对任意一棵二叉树对任意一棵二叉树对任意一棵二叉树BTBTBTBT，如果其叶子结点数为，如果其叶子结点数为，如果其叶子结点数为，如果其叶子结点数为n n n n0 0 0 0，度为，度为，度为，度为2 2 2 2的结点数为的结点数为的结点数为的结点数为n n n n2 2 2 2，则，则，则，则n n
15、n n0 0 0 0n n n n2 2 2 21 1 1 1。 证明：证明：设二叉树设二叉树BTBT中度为中度为1 1的结点数为的结点数为n n1 1，因为二叉树中所，因为二叉树中所有结点的度均小于或等于有结点的度均小于或等于2 2，所以二叉树，所以二叉树BTBT的结点总数为：的结点总数为： n=nn=n0 0+n+n1 1+n+n2 2 （1 1） 另一方面，在二叉树中，度为另一方面，在二叉树中，度为1 1的结点有的结点有1 1个孩子，度为个孩子，度为2 2的的结点有结点有2 2个孩子，故二叉树中孩子结点的总数为个孩子，故二叉树中孩子结点的总数为n n1 1+2n+2n2 2。由于二。由于
16、二叉树中只有根结点不是任何结点的孩子，因此，二叉树中的结叉树中只有根结点不是任何结点的孩子，因此，二叉树中的结点总数又可以表示为：点总数又可以表示为： n=nn=n1 1+2n+2n2 2+1 +1 （2 2）将式（将式（1 1）与式（）与式（2 2）合并，并整理后可得：）合并，并整理后可得： n n0 0n n2 21 1故结论成立。故结论成立。第 章 树 和 二 叉 树 满二叉树：满二叉树：一棵深度为一棵深度为k k且有且有2 2k k-1-1个结点个结点的二叉树称为满二叉树。的二叉树称为满二叉树。 完全二叉树：完全二叉树：深度为深度为k k，有，有n n个结点的二个结点的二叉树当且仅当其
17、每一个结点都与深度为叉树当且仅当其每一个结点都与深度为k k的的满二叉树中编号从满二叉树中编号从1 1至至n n的结点一一对应时，的结点一一对应时，称为完全二叉树。称为完全二叉树。为方便对性质为方便对性质4 4的讨论，介绍两类特殊形态的讨论，介绍两类特殊形态的二叉树。的二叉树。满二叉树和完全二叉树满二叉树和完全二叉树第 章 树 和 二 叉 树 满二叉树的特点：满二叉树的特点：每一层上的结点数都具每一层上的结点数都具有最大结点数。有最大结点数。完全二叉树的特点：完全二叉树的特点：叶子结点只可能在层叶子结点只可能在层次最大的两层上出现，对任一结点，若其次最大的两层上出现，对任一结点，若其右分支下子
18、孙的最大层次为右分支下子孙的最大层次为p p，则其左分，则其左分支下子孙的最大层次必为支下子孙的最大层次必为p p或或p+1p+1。下图所。下图所示的二叉树即为完全二叉树。满二叉树必示的二叉树即为完全二叉树。满二叉树必为完全二叉树，而完全二叉树不一定是满为完全二叉树，而完全二叉树不一定是满二叉树。二叉树。第 章 树 和 二 叉 树 二叉树的性质二叉树的性质：性质性质性质性质4 4 4 4 具有具有具有具有n n n n个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为个结点的完全二叉树的深度为 loglogloglog2 2 2 2n n n n 1 1 1 1。
19、（符号（符号（符号（符号 x x x x 表示不大于表示不大于表示不大于表示不大于x x x x的最大整数。）的最大整数。）的最大整数。）的最大整数。） 证明：证明：假设具有假设具有n n个结点的完全二叉树其深度为个结点的完全二叉树其深度为k k，根据，根据性质性质2 2可知，可知，k-1k-1层满二叉树的结点总数为：层满二叉树的结点总数为：2 2k-1k-11 1，而，而k k 层层满二叉树的结点总数为满二叉树的结点总数为2 2k-1k-1，根据完全二叉树的定义可以得到：，根据完全二叉树的定义可以得到： 2 2k-1k-11 1n2n2k k-1-1于是有于是有 2 2k-1k-1nn2 2
20、k k对对上上式式取取对对数数，得得到到：k k1log1log2 2n nk k，因因为为k k是是整整数数，所所以以有：有：k-1k-1 loglog2 2n n ，即，即k k loglog2 2n n +1+1第 章 树 和 二 叉 树 性质性质性质性质5 5 5 5 对于具有对于具有对于具有对于具有n n n n个结点的完全二叉树，如果对个结点的完全二叉树，如果对个结点的完全二叉树，如果对个结点的完全二叉树，如果对其结点按层次编号，则对任一结点其结点按层次编号，则对任一结点其结点按层次编号，则对任一结点其结点按层次编号，则对任一结点i(1in)i(1in)i(1in)i(1in)，有
21、：有：有：有： (1) (1) (1) (1) 如果如果如果如果i=1i=1i=1i=1，则结点，则结点，则结点，则结点i i i i是二叉树的根，无双亲；是二叉树的根，无双亲；是二叉树的根，无双亲；是二叉树的根，无双亲；如果如果如果如果i1i1i1i1，则其双亲是，则其双亲是，则其双亲是，则其双亲是 i/2i/2i/2i/2 (2) (2) (2) (2) 如果如果如果如果2in2in2in2in，则结点，则结点，则结点，则结点i i i i无左孩子；如果无左孩子；如果无左孩子；如果无左孩子；如果2in2in2in2in，则其左孩子是则其左孩子是则其左孩子是则其左孩子是2i2i2i2i (3
22、) (3) (3) (3) 如果如果如果如果2i+1n2i+1n2i+1n2i+1n，则结点，则结点，则结点，则结点i i i i无右孩子；如果无右孩子；如果无右孩子；如果无右孩子；如果2i+1n2i+1n2i+1n2i+1n，则其右孩子是，则其右孩子是，则其右孩子是，则其右孩子是2i+12i+12i+12i+1第 章 树 和 二 叉 树 二叉树的存储结构二叉树的存储结构顺序存储结构顺序存储结构顺序存储结构顺序存储结构: : : :为了能够反映出结点之间的逻辑为了能够反映出结点之间的逻辑为了能够反映出结点之间的逻辑为了能够反映出结点之间的逻辑关系，必须将它关系，必须将它关系，必须将它关系，必须
23、将它“修补修补修补修补”成完全二叉树，对应下成完全二叉树，对应下成完全二叉树，对应下成完全二叉树，对应下面的完全二叉树，可以开辟长度为面的完全二叉树，可以开辟长度为面的完全二叉树，可以开辟长度为面的完全二叉树，可以开辟长度为11111111的数组，对的数组，对的数组，对的数组，对11111111个数据元素进行存储，原二叉树中空缺的结点个数据元素进行存储，原二叉树中空缺的结点个数据元素进行存储，原二叉树中空缺的结点个数据元素进行存储，原二叉树中空缺的结点在数组中的相应单元必须置空在数组中的相应单元必须置空在数组中的相应单元必须置空在数组中的相应单元必须置空 a a b b c c d d e e
24、 f f g g第 章 树 和 二 叉 树 二叉树的存储结构二叉树的存储结构 链式存储结构链式存储结构链式存储结构链式存储结构 : : : :表示二叉树的链表中的结点应该包含表示二叉树的链表中的结点应该包含表示二叉树的链表中的结点应该包含表示二叉树的链表中的结点应该包含3 3 3 3个域：个域：个域：个域：数据域和指向左、右子树的指针域，二叉树的这种存储结构被称数据域和指向左、右子树的指针域，二叉树的这种存储结构被称数据域和指向左、右子树的指针域，二叉树的这种存储结构被称数据域和指向左、右子树的指针域，二叉树的这种存储结构被称为二叉链表。为二叉链表。为二叉链表。为二叉链表。 LchildLch
25、ilddatadatarchildrchild在n个结点的二叉链表中，有n+1个空指针域第 章 树 和 二 叉 树 6.3 6.3 二叉树的遍历与线索化二叉树的遍历与线索化 二叉树的遍历：二叉树的遍历：二叉树的遍历：二叉树的遍历：是按某条搜索路径访问树中的每是按某条搜索路径访问树中的每是按某条搜索路径访问树中的每是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且一个结点，使得每一个结点均被访问一次，而且一个结点，使得每一个结点均被访问一次，而且一个结点，使得每一个结点均被访问一次，而且仅被访问一次。仅被访问一次。仅被访问一次。仅被访问一次。 先根遍历二叉树先根遍历二叉树先根
26、遍历二叉树先根遍历二叉树 （1 1 1 1）访问根结点；）访问根结点；）访问根结点；）访问根结点； （2 2 2 2）先根遍历左子树；）先根遍历左子树；）先根遍历左子树；）先根遍历左子树； （3 3 3 3）先根遍历右子树。）先根遍历右子树。）先根遍历右子树。）先根遍历右子树。 第 章 树 和 二 叉 树 中根遍历二叉树中根遍历二叉树中根遍历二叉树中根遍历二叉树（1 1 1 1）中根遍历左子树；）中根遍历左子树；）中根遍历左子树；）中根遍历左子树；（2 2 2 2）访问根结点；）访问根结点；）访问根结点；）访问根结点；（3 3 3 3）中根遍历右子树。）中根遍历右子树。）中根遍历右子树。）中根
27、遍历右子树。 后根遍历二叉树后根遍历二叉树后根遍历二叉树后根遍历二叉树 （1 1 1 1）后根遍历左子树；）后根遍历左子树；）后根遍历左子树；）后根遍历左子树； （2 2 2 2）后根遍历右子树；）后根遍历右子树；）后根遍历右子树；）后根遍历右子树；（3 3 3 3）访问根结点。）访问根结点。）访问根结点。）访问根结点。 第 章 树 和 二 叉 树 先根遍历先根遍历先根遍历先根遍历: -+a*b: -+a*b: -+a*b: -+a*b cd/efcd/efcd/efcd/ef中根遍历中根遍历中根遍历中根遍历: a+b*c: a+b*c: a+b*c: a+b*c d d d d e/fe/f
28、e/fe/f后根遍历后根遍历后根遍历后根遍历: abcd-*+ef/-: abcd-*+ef/-: abcd-*+ef/-: abcd-*+ef/- 第 章 树 和 二 叉 树 typedef struct Nodestruct Node datatype data; datatype data; struct Node *Lchild; struct Node *Lchild; struct Node *Rchild; struct Node *Rchild; BTnode,*Btree; 二叉树结点的存储类型二叉树结点的存储类型第 章 树 和 二 叉 树 先根遍历算法先根遍历算法void
29、preorder(Btree root) if(root!=NULL) Visit(root-data);/访问根结点访问根结点 preorder(root-Lchild);/递归访问左子树递归访问左子树 preorder(root-Rchild);/递归访问右子树递归访问右子树 第 章 树 和 二 叉 树 中根遍历算法中根遍历算法void inorder(Btree t) if(t!=NULL)inorder(t-Lchild);Visit(t-data);inorder(t-Rchild);第 章 树 和 二 叉 树 一棵二叉树一棵二叉树中根遍历二叉树的搜索路线中根遍历二叉树的搜索路线第
30、章 树 和 二 叉 树 后根遍历算法后根遍历算法void PostOrder(Btree root)if(root!=NULL) PostOrder(root-Lchild); PostOrder(root-Rchild); Visit(root -data); 第 章 树 和 二 叉 树 中序遍历二叉树的非递归算法中序遍历二叉树的非递归算法这在遍历的过程中要用栈来保存遍历中经过的路径。这在遍历的过程中要用栈来保存遍历中经过的路径。void inorder(Btree root)void inorder(Btree root)Btree q; Btree q; /工作指针工作指针int top
31、int top，bb; bb; /栈顶指针栈顶指针toptopBtnode smax;Btnode smax;/数组的每个元素是链表结点，数组的每个元素是链表结点，s s当做栈当做栈top=0; top=0; /栈初始化栈初始化q=root; q=root; /工作指针赋初值工作指针赋初值bb=0; bb=0; /在操作过程中，当栈空或栈满时为在操作过程中，当栈空或栈满时为1 1第 章 树 和 二 叉 树 While(bb!=1)While(bb!=1) if(q!=NULL)if(q!=NULL) top=top+1; top=top+1; if(topmax) if(topmax) bb=
32、1;printf( bb=1;printf(“栈满了栈满了”) )； else else /入栈入栈 stop=q; q=q-Lchild;stop=q; q=q-Lchild; else else if(top=0) if(top=0) /当当toptop为为0 0时，说明这棵树遍历完了时，说明这棵树遍历完了 bb=1;bb=1; else else q=stop; q=stop; /出栈，栈顶元素赋给出栈，栈顶元素赋给q q top=top-1; top=top-1; printf( printf(“访问访问q-dataq-data”); ); /访问出栈的根结点访问出栈的根结点 q=q-
33、Rchild; q=q-Rchild; /搜索右子树搜索右子树 第 章 树 和 二 叉 树 利用二叉链表剩余的利用二叉链表剩余的n+1n+1个空指个空指针域来存放遍历过程中结点的前驱和针域来存放遍历过程中结点的前驱和后继的指针，这种附加的指针称为后继的指针，这种附加的指针称为“线索线索”，加上了线索的二叉链表称为，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索链表，相应的二叉树称为线索二线索二叉树叉树。线索二叉树线索二叉树第 章 树 和 二 叉 树 为了区分结点的指针域是指向其为了区分结点的指针域是指向其孩子的指针，还是指向其前驱或后孩子的指针，还是指向其前驱或后继的线索，可在二叉链表
34、的结点中继的线索，可在二叉链表的结点中, ,再增设再增设2 2个标志域。个标志域。LchildLchildLchildLchildLtagLtagLtagLtagDataDataDataDataRtagRtagRtagRtagRchildRchildRchildRchild第 章 树 和 二 叉 树 对二叉树以某种次序进行遍历并且对二叉树以某种次序进行遍历并且加上线索的过程叫做加上线索的过程叫做线索化线索化 线索化是将二叉链表中的空链域填线索化是将二叉链表中的空链域填上相应结点在一定遍历次序下的前驱或上相应结点在一定遍历次序下的前驱或后继结点的地址。因此后继结点的地址。因此线索化的过程就线索化
35、的过程就是在遍历过程中修改空链域的过程是在遍历过程中修改空链域的过程。 对二叉树按照不同的遍历次序进行对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树。线索化，可以得到不同的线索二叉树。第 章 树 和 二 叉 树 0 Lchild0 Lchild指向结点的左孩子指向结点的左孩子 Ltag=Ltag= 1 Lchild1 Lchild指向该结点的前驱指向该结点的前驱 0 Rchild0 Rchild指向该结点的右孩子指向该结点的右孩子 Rtag= Rtag= 1 Rchild 1 Rchild指向该结点的后继指向该结点的后继左标志的含义左标志的含义右标志的含义右标志的含义第 章 树
36、 和 二 叉 树 typedef typedef struct Nodestruct Node datatype data; datatype data; struct Node *Lchild; struct Node *Lchild; struct Node *Rchild; struct Node *Rchild; int Ltag, Rtag; int Ltag, Rtag; ThreadTnode,*ThreadTtree; ThreadTnode,*ThreadTtree;LchildLchildLchildLchildLtagLtagLtagLtagDataDataDataDat
37、aRtagRtagRtagRtagRchildRchildRchildRchild线索二叉树的数据类型定义为：线索二叉树的数据类型定义为：第 章 树 和 二 叉 树 中序线索二叉树中序线索二叉树中序线索二叉树示例中序线索二叉树示例第 章 树 和 二 叉 树 建立一棵中序线建立一棵中序线索树的递归算法索树的递归算法中根遍历线索化( (给二叉树穿线) )的算法。ThreadTtree pre=NULL;ThreadTtree pre=NULL;Void Inthread (ThreadTtree root)Void Inthread (ThreadTtree root) if (root != N
38、ULL) if (root != NULL) /树不空时树不空时 Inthread(root-Lchild); Inthread(root-Lchild); if(root-Lchild= =NULL)if(root-Lchild= =NULL)/左孩子空则穿线，改左标志左孩子空则穿线，改左标志 root-Ltag=1; root-Lchild=pre; root-Ltag=1; root-Lchild=pre; if(pre!=NULL& pre-Rchild=NULL) if(pre!=NULL& pre-Rchild=NULL) /建右线索建右线索 pre- Rchild=root; p
39、re-Rtag=1; pre- Rchild=root; pre-Rtag=1; pre=root pre=root； / pre/ pre指向刚刚访问过的结点指向刚刚访问过的结点 Inthread(root-Rchild); Inthread(root-Rchild); 第 章 树 和 二 叉 树 遍历中根线索二叉树的算法。Void InthreadTrav (ThreadTtree root)Void InthreadTrav (ThreadTtree root) ThreadTtree h; ThreadTtree h; if (root = NULL) return; if (root
40、 = NULL) return; /树空退出树空退出 h=root; h=root; while(h-Ltag=0) while(h-Ltag=0) h=h-Lchild; h=h-Lchild; printf(printf(“%c %c ”,h-data);,h-data); while(h-rchild!=NULL) while(h-rchild!=NULL) if(h-Rtag=1) h=h-Rchild; if(h-Rtag=1) h=h-Rchild; else else h=h-Rchild; h=h-Rchild; while(h-Ltag=0) while(h-Ltag=0)
41、h=h-Lchild; h=h-Lchild; printf( printf(“%c %c ”,h-data);,h-data); 遍历一棵中序线遍历一棵中序线索树的非递归算法索树的非递归算法第 章 树 和 二 叉 树 建立建立中序中序线索树的线索树的非递归算法非递归算法(在建好的二叉链表结在建好的二叉链表结构上穿线构上穿线),就是在中序遍历的算法中就是在中序遍历的算法中,访问根结点的同时访问根结点的同时,将空链域逐个用线索代替将空链域逐个用线索代替。在穿线过程中要用栈来保存遍历在穿线过程中要用栈来保存遍历中经过的路径，才能访问到二叉树中的每一个结点中经过的路径，才能访问到二叉树中的每一个结点
42、。ThreadTtreeThreadTtreetbtree(ThreadTtreeThreadTtreet)/t是二叉链表的表头指针是二叉链表的表头指针ThreadTtreeThreadTtreesmax,p,pr;/s是指针数组，是栈是指针数组，是栈inttop;/top是栈顶指针是栈顶指针pr=Null;/初始化指针初始化指针pr,pr是是p的前驱指针的前驱指针top=0;/初始化栈顶指针初始化栈顶指针topp=t;/p为工作指针，开始时指向根为工作指针，开始时指向根第 章 树 和 二 叉 树 while(p!=Null|top!=0)while(p!=Null)top+;stop=p;p
43、=p-Lchild;/p入栈并继续搜索入栈并继续搜索p的左子树的左子树if(top!=0)/栈不空，出栈并穿线索，包括左线索和右线索栈不空，出栈并穿线索，包括左线索和右线索p=stop;top-;printf(“%c”,p-data);/出栈出栈,放入放入p中，访问中，访问p结点结点if(p-Lchild=Null)/p无左孩子，无左孩子，p是刚退栈的结点是刚退栈的结点p-Ltag=1;p-Lchild=pr;/p的左孩子指向的左孩子指向p的前驱的前驱elsep-Ltag=0;/p有左孩子，修改左标志为有左孩子，修改左标志为0。这时。这时p的左链已指向其左孩子的左链已指向其左孩子if(pr!=
44、NUll)/前驱前驱pr不为空不为空if(pr-Rchild=Null)pr-Rchild=p;pr-Rtag=1;elsepr-Rtag=0;/pr有右孩子时令有右孩子时令p的前驱的前驱pr的右标志为的右标志为0pr=p;p=p-Rchild;/修改修改pr，继续搜索，继续搜索p的右子树的右子树pr-Rtag=1;/最后一个结点无后继最后一个结点无后继可在此举检索结点的例子。可在此举检索结点的例子。abdcef第 章 树 和 二 叉 树 基于遍历的应用与线索二叉树的应用基于遍历的应用与线索二叉树的应用 二叉树的遍历是对二叉树进行各种运算的二叉树的遍历是对二叉树进行各种运算的二叉树的遍历是对二
45、叉树进行各种运算的二叉树的遍历是对二叉树进行各种运算的一个重要基础，一个重要基础，一个重要基础，一个重要基础，对访问（程序中的对访问（程序中的对访问（程序中的对访问（程序中的visitvisitvisitvisit函数）函数）函数）函数）结点可理解为对二叉树结点的各种操作结点可理解为对二叉树结点的各种操作结点可理解为对二叉树结点的各种操作结点可理解为对二叉树结点的各种操作。因此，。因此，。因此，。因此，只要将二叉树三种遍历算法中的只要将二叉树三种遍历算法中的只要将二叉树三种遍历算法中的只要将二叉树三种遍历算法中的visitvisitvisitvisit函数具体函数具体函数具体函数具体化，就产生
46、了基于二叉树的不同应用。化，就产生了基于二叉树的不同应用。化，就产生了基于二叉树的不同应用。化，就产生了基于二叉树的不同应用。 第 章 树 和 二 叉 树 输出输出( (先根先根) )二叉树中的结点二叉树中的结点 Void paintnode (Btree root) Void paintnode (Btree root) if (root!=NULL) if (root!=NULL) printf (root -data); printf (root -data); paintnode (root -Lchild); paintnode (root -Lchild); paintnode (
47、root -Rchild); paintnode (root -Rchild); 第 章 树 和 二 叉 树 输出（先根）二叉树中的叶子结点输出（先根）二叉树中的叶子结点Void paintleaf (Btree root) Void paintleaf (Btree root) / root/ root是指向根结点的指针是指向根结点的指针 if (root!=NULL) if (root!=NULL) if(root-Lchild= =NULL & root-Rchild= =NULL)if(root-Lchild= =NULL & root-Rchild= =NULL)printf (ro
48、ot -data);printf (root -data);paintleaf (root -Lchild);paintleaf (root -Lchild);paintleaf (root -Rchild);paintleaf (root -Rchild); 第 章 树 和 二 叉 树 统计叶子结点数目（统计叶子结点数目（后根遍历）后根遍历） Void leafcount(Btree root)Void leafcount(Btree root) if(root!=NULL)if(root!=NULL) leafcount(root-Lchild);leafcount(root-Lchild
49、);leafcount(root-Rchild);leafcount(root-Rchild);if (root-Lchild= =NULL & root-Rchild= =NULL)if (root-Lchild= =NULL & root-Rchild= =NULL)count+;count+; 提示：提示：提示：提示：countcountcountcount为全局变量，也可在主函数中定义。为全局变量，也可在主函数中定义。为全局变量，也可在主函数中定义。为全局变量，也可在主函数中定义。第 章 树 和 二 叉 树 建立二叉树建立二叉树图图图图中中中中二二二二叉叉叉叉树树树树的的的的先先先先根
50、根根根遍遍遍遍历历历历序序序序列列列列为为为为：ABDGCEHFABDGCEHFABDGCEHFABDGCEHF，而而而而考考考考虑虑虑虑空空空空子子子子树树树树后后后后的的的的先先先先根根根根遍遍遍遍历历历历序序序序列列列列( ( ( (空空空空子子子子树树树树用用用用一一一一个个个个特特特特定定定定的的的的符符符符号号号号代代代代替替替替, , , ,这这这这里里里里用用用用.).).).)应应应应为为为为：ABD.G.CE.HFABD.G.CE.HFABD.G.CE.HFABD.G.CE.HF，其其其其中中中中“ “. . . .” ”代表空子树。代表空子树。代表空子树。代表空子树。第
51、章 树 和 二 叉 树 如如如如果果果果已已已已知知知知二二二二叉叉叉叉树树树树的的的的考考考考虑虑虑虑了了了了空空空空子子子子树树树树后后后后的的的的先先先先根根根根遍遍遍遍历历历历序序序序列列列列，那那那那么么么么建建建建立这棵二叉树的算法如下立这棵二叉树的算法如下立这棵二叉树的算法如下立这棵二叉树的算法如下( ( ( (假定假定假定假定datatypedatatypedatatypedatatype类型为类型为类型为类型为char)char)char)char)： void CreateBtree(Btree bt)void CreateBtree(Btree bt) /先根遍历先根遍历
52、 char ch;char ch; ch=getchar(); ch=getchar(); if(ch= =.) if(ch= =.) bt=NULL; bt=NULL; /生成空子树生成空子树 elseelse bt=(Btree)malloc(sizeof(BTnode); bt=(Btree)malloc(sizeof(BTnode); /申请结点申请结点 bt-data= ch; bt-data= ch; /为结点的数据域赋值为结点的数据域赋值 CreateBiTree( bt-Lchild ); CreateBiTree( bt-Lchild ); /生左子树生左子树 CreateB
53、iTree( bt-Rchild ); CreateBiTree( bt-Rchild ); /生右子树生右子树 第 章 树 和 二 叉 树 求二叉树的高度求二叉树的高度采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：采用递归的方法定义二叉树的高度：（1 1 1 1）若二叉树为空，则高度为）若二叉树为空，则高度为）若二叉树为空，则高度为）若二叉树为空，则高度为0 0 0 0；（2 2 2 2）若二叉树非空，其高度应为其左、右）若二叉树非空，其高度应为其左、右）若二叉树非空，其高度应为其左、右）若二叉树非空，其高度应为其左、右子树高度的最大值加子树
54、高度的最大值加子树高度的最大值加子树高度的最大值加1 1 1 1。 第 章 树 和 二 叉 树 int TreeDepth(Btree bt) int TreeDepth(Btree bt) int hl,hr,max; int hl,hr,max; if(bt!=NULL) if(bt!=NULL) hl=TreeDepth(bt-Lchild); hl=TreeDepth(bt-Lchild);/左子树的高度左子树的高度 hr=TreeDepth(bt-Rchild);hr=TreeDepth(bt-Rchild);/右子树的高度右子树的高度 max = (hlmax = (hl，hr);
55、 hr); /取左、右子树高度的最大者取左、右子树高度的最大者 return(max+1);return(max+1); else return(0); else return(0); 第 章 树 和 二 叉 树 在中根遍历的线索树中查找前驱结点在中根遍历的线索树中查找前驱结点 对二叉树中任意结点对二叉树中任意结点p p，找其前驱结点，找其前驱结点, ,有有两种情况：两种情况： 当结点当结点p p的左标志的左标志p-Ltag=1p-Ltag=1时，则时，则p p的左孩子的左孩子p-Lchildp-Lchild即为即为p p的前驱结点；的前驱结点； 当结点当结点p p的左标志的左标志p-Ltag
56、=0p-Ltag=0时，说时，说明明p p有左子树，此时有左子树，此时p p的中根遍历下的前驱的中根遍历下的前驱结点即为其左子树右链下的最后一个结点。结点即为其左子树右链下的最后一个结点。 第 章 树 和 二 叉 树 ThreadTnode *pre; ThreadTnode *pre; /p/p的前驱的前驱ThreadTnode Previ (ThreadTnode * p)ThreadTnode Previ (ThreadTnode * p) ThreadTnode *q; ThreadTnode *q; if(p-Ltag= =1) if(p-Ltag= =1) /p/p无左孩子无左孩子
57、 pre = p-Lchild; pre = p-Lchild; else else /p/p有左孩子有左孩子 for( for(q = p-Lchild;q = p-Lchild; q-Rtag= =0; q-Rtag= =0; q =q-Rchild q =q-Rchild);); pre=q; pre=q; 第 章 树 和 二 叉 树 ThreadTnode Previ(ThreadTnode * p)ThreadTnode Previ(ThreadTnode * p) ThreadTnode *q; ThreadTnode *q; if(p-Ltag= =1) if(p-Ltag= =
58、1) return(p-Lchild); return(p-Lchild); q = p-Lchild; q = p-Lchild; while(q-Rtag= =0) while(q-Rtag= =0) q = p-Rchild; q = p-Rchild; return(q); return(q); 第 章 树 和 二 叉 树 在中根遍历的线索树中查找后继结点在中根遍历的线索树中查找后继结点 对二叉树中任意结点对二叉树中任意结点p p，要找其后继，要找其后继结点，有两种情况：结点，有两种情况： 当当p-Rtag=1p-Rtag=1时，时，p-Rchildp-Rchild即即为为p p的后继
59、结点；的后继结点； 当当p-Rtag=0p-Rtag=0时，说明时，说明p p有右子有右子树，此时树，此时p p的中根遍历下的后继结点的中根遍历下的后继结点即为其右子树左链下的最后一个结点。即为其右子树左链下的最后一个结点。 第 章 树 和 二 叉 树 ThreadTnode Succedent(ThreadTnode *p)ThreadTnode Succedent(ThreadTnode *p) ThreadTnode *q; ThreadTnode *q; if (p-Rtag = =1) if (p-Rtag = =1) return(p-Rchild); return(p-Rchil
60、d); else else for(q = p-RChild; for(q = p-RChild; q-Ltag = =0 ; q-Ltag = =0 ; q =q-LChild ); q =q-LChild ); return(q); return(q); 在中根在中根在中根在中根遍历线遍历线遍历线遍历线索树中索树中索树中索树中对二叉对二叉对二叉对二叉树中任树中任树中任树中任意结点意结点意结点意结点p p p p，找，找，找，找其后继其后继其后继其后继结点结点结点结点q q的算法的算法第 章 树 和 二 叉 树 void Btree (ThreadTnode * t)void Btree (
61、ThreadTnode * t) ThreadTnode *p; ThreadTnode *p; if(t= =NULL)return; if(t= =NULL)return; p=t; p=t; while(p-Ltag=0) p = p-Lchild; while(p-Ltag=0) p = p-Lchild; doprintf( doprintf( “输出输出 p-datap-data” ); ); p=Succedent(p);while(p!=Null); p=Succedent(p);while(p!=Null); 遍历线索二树遍历线索二树第 章 树 和 二 叉 树 在在中序中序线
62、索树插入结点作为双亲结点的右孩子（右线索树插入结点作为双亲结点的右孩子（右子树）的子树）的算法。算法。设插入结点为设插入结点为r，插入后作为，插入后作为p结点的右子树的根结点的右子树的根分两种情况：分两种情况：1、原结点、原结点p没有右子树没有右子树第 章 树 和 二 叉 树 2、原结点、原结点p有右子树有右子树第 章 树 和 二 叉 树 ThreadTtreeThreadTtreetbtree(ThreadTtreeThreadTtreep)/p是二叉链表中的一个结点指针，插入一个结点是二叉链表中的一个结点指针，插入一个结点r作为结点作为结点p右子树的根右子树的根ThreadTtreeThr
63、eadTtreer,q;/q是结点是结点p的前驱结点的指针的前驱结点的指针r=(r=(ThreadTtreeThreadTtree)malloc(sizeof()malloc(sizeof(ThreadTnodeThreadTnode););r-data=*;r-Rchild=p-Rchild;r-Rtag=p-Rtag;r-Lchild=p;/r的左孩子指向前驱的左孩子指向前驱r-Ltag=1;第 章 树 和 二 叉 树 if(p-Rtag=0)/说明说明p有右孩子有右孩子q=p-Rchild;/工作指针工作指针q指向指向p的右孩子的右孩子while(q-Ltag=0)/找找q的最左下的结点
64、的最左下的结点q=q-Lchild;q-Lchild=r;/修改修改q的左线索为的左线索为rp-Rchild=r;p-Rtag=0;举检索结点的例子举检索结点的例子第 章 树 和 二 叉 树 6.4 6.4 树和森林树和森林树的存储结构树的存储结构 双亲（链表）表示法双亲（链表）表示法双亲（链表）表示法双亲（链表）表示法 用一组连续的存储空间（数组）来存储树中的结用一组连续的存储空间（数组）来存储树中的结用一组连续的存储空间（数组）来存储树中的结用一组连续的存储空间（数组）来存储树中的结点，每个数组元素中不但包含结点本身的信息，还保点，每个数组元素中不但包含结点本身的信息，还保点，每个数组元素
65、中不但包含结点本身的信息，还保点，每个数组元素中不但包含结点本身的信息，还保存该结点双亲结点在数组中的下标号。数组中每个结存该结点双亲结点在数组中的下标号。数组中每个结存该结点双亲结点在数组中的下标号。数组中每个结存该结点双亲结点在数组中的下标号。数组中每个结点含两个域：点含两个域：点含两个域：点含两个域： 数据域：数据域：数据域：数据域：存放结点本身信息存放结点本身信息存放结点本身信息存放结点本身信息 双亲域：双亲域：双亲域：双亲域：指示本结点的双亲结点在数组中位置指示本结点的双亲结点在数组中位置指示本结点的双亲结点在数组中位置指示本结点的双亲结点在数组中位置第 章 树 和 二 叉 树 #d
66、efine Maxsize 50#define Maxsize 50typedef typedef struct Nodestruct Node DataType data; DataType data;/*/*数据域数据域* */ / int parent; int parent; /*/*双亲域双亲域* */ / Tnode;Tnode; Tnode Tnode ptreeMaxsize;ptreeMaxsize; 在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：在双亲表示法下，树的数据类型定义如下：第 章 树 和 二 叉
67、树 abcdefhgiacdefghib112235551601234578dataparent如何找孩子结点如何找孩子结点ptreeptree 数组数组双亲（链表）表示法示意图双亲（链表）表示法示意图双亲（链表）表示法示意图双亲（链表）表示法示意图 第 章 树 和 二 叉 树 孩子链表表示法孩子链表表示法孩子链表表示法孩子链表表示法 把每个结点的孩子结点排列起来，构成一个单链表，该单链表把每个结点的孩子结点排列起来，构成一个单链表，该单链表把每个结点的孩子结点排列起来，构成一个单链表，该单链表把每个结点的孩子结点排列起来，构成一个单链表，该单链表就是本结点的孩子链表。具有就是本结点的孩子链表
68、。具有就是本结点的孩子链表。具有就是本结点的孩子链表。具有n n n n个结点的树就形成了个结点的树就形成了个结点的树就形成了个结点的树就形成了n n n n个孩子链表。个孩子链表。个孩子链表。个孩子链表。 v孩子结点#define Maxsize 50#define Maxsize 50typedef typedef struct ChildNodestruct ChildNode int Child;int Child;struct ChildNode * next;struct ChildNode * next; ChildNode;ChildNode;v表头结点typedef type
69、def structstruct DataType data; DataType data; ChildNode * ChildHead ; ChildNode * ChildHead ; DataNode;DataNode;v 孩子链表的表头数据组 DataNode DataNode CtreeMaxsizeCtreeMaxsize; ;第 章 树 和 二 叉 树 孩子链表表示法示意图孩子链表表示法示意图孩子链表表示法示意图孩子链表表示法示意图第 章 树 和 二 叉 树 孩子兄弟链表表示法孩子兄弟链表表示法孩子兄弟链表表示法孩子兄弟链表表示法 又称为二叉链表表示法，即以二叉链表作为树的存储结
70、构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链又称为二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟是，这两个链域分别指向该结点的第
71、一个孩子结点和下一个兄弟（右兄弟）。（右兄弟）。（右兄弟）。（右兄弟）。 FirstChildFirstChilddatadataNextsiblingNextsiblingtypedef typedef struct CSNodestruct CSNode DataType data; DataType data; Struct CSNode *FirstChild, *Nextsibling; Struct CSNode *FirstChild, *Nextsibling; * CSTree; * CSTree;第 章 树 和 二 叉 树 将此图所示的树向左下方旋转将此图所示的树向左下方旋
72、转45度，就会得到一棵二叉树度，就会得到一棵二叉树孩子兄弟链表表示法示意图孩子兄弟链表表示法示意图孩子兄弟链表表示法示意图孩子兄弟链表表示法示意图第 章 树 和 二 叉 树 对应对应结论：树的结论：树的结论：树的结论：树的孩子兄弟链表表示法与对应二叉树的二叉链表表示法相同。孩子兄弟链表表示法与对应二叉树的二叉链表表示法相同。孩子兄弟链表表示法与对应二叉树的二叉链表表示法相同。孩子兄弟链表表示法与对应二叉树的二叉链表表示法相同。因此，上图中的树与二叉树之间存在相互转换的关系。因此，上图中的树与二叉树之间存在相互转换的关系。因此，上图中的树与二叉树之间存在相互转换的关系。因此，上图中的树与二叉树之
73、间存在相互转换的关系。第 章 树 和 二 叉 树 ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空树转换为二叉树树转换为二叉树树转换为二叉树树转换为二叉树 v 抹线：对树中每个结点，除了其左孩子外抹去该结点与其余抹线：对树中每个结点，除了其左孩子外抹去该结点与其余孩子之间的连线。孩子之间的连线。v 加线：在树中所有相邻的兄弟之间加一连线；加线：在树中所有相邻的兄弟之间加一连线；v 整理：以树的根结点为轴心，将整树顺时针转整理：以树的根结点为轴心，将整树顺时针转4545。 第 章 树 和 二
74、 叉 树 森林转换成二叉树森林转换成二叉树森林转换成二叉树森林转换成二叉树vv 将各棵树分别转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树将各棵树分别转换成二叉树vv 将每棵树的根结点用线相连将每棵树的根结点用线相连将每棵树的根结点用线相连将每棵树的根结点用线相连vv 以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构顺时针旋转，构成二叉树型结构ABCDEF
75、GHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第 章 树 和 二 叉 树 二叉二叉二叉二叉树转换成树树转换成树树转换成树树转换成树vv加线：若加线：若加线：若加线：若p p p p结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将结点是双亲结点的左孩子，则将p p p p的右孩子，右的右孩子，右的右孩子，右的右孩子，右孩子的右孩子，孩子的右孩子，孩子的右孩子，孩子的右孩子，沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与沿分支找到的所有右孩子，都与p p p p的的的的双亲用线连起来双亲用线连起来双亲用
76、线连起来双亲用线连起来vv抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线抹线：抹掉原二叉树中双亲与右孩子之间的连线vv调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构调整：将结点按层次排列，形成树结构ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI第 章 树 和 二 叉 树 二叉树转换成森林二叉树转换成森林二叉树转换成森林二叉树转换成森林vv 抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩
77、子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树vv 还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树还原：将孤立的二叉树还原成树ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ第 章 树 和 二 叉 树 树和森林的遍历树和森林的遍历先根遍历先根遍历
78、 若树非空，则遍历方法为：若树非空，则遍历方法为： a.a.访问根结点。访问根结点。 b.b.从左到右，依次先根遍历根结点的每一棵从左到右，依次先根遍历根结点的每一棵子树。子树。一、树的遍历一、树的遍历一、树的遍历一、树的遍历第 章 树 和 二 叉 树 若树非空，则遍历方法为：若树非空，则遍历方法为： a.a.从左到右，依次后根遍历根结点的每从左到右，依次后根遍历根结点的每一棵子树。一棵子树。 b.b.访问根结点。访问根结点。树的后根遍历树的后根遍历第 章 树 和 二 叉 树 若树非空，则遍历方法为：若树非空，则遍历方法为： 先访问第一层上的结点，然后依次先访问第一层上的结点，然后依次遍历第二
79、层，遍历第二层，第第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第 章 树 和 二 叉 树 二、森林的遍历二、森林的遍历若森林非空，则遍历方法为：若森林非空，则遍历方法为： a. a. 访问森林中第一棵树的根结点。访问森林中第一棵树的根结点。 b.b.先根遍历第一棵树的根结点的子树森林。先根遍历第一棵树的根结点的子树森林。 c.c.先根遍历除去第一棵树之
80、后剩余的树构成的先根遍历除去第一棵树之后剩余的树构成的森林。森林。森林的森林的先根遍历先根遍历树和森林的遍历树和森林的遍历第 章 树 和 二 叉 树 若森林非空，则遍历方法为：若森林非空，则遍历方法为：a.中根遍历森林中第一棵树的根结点的子树中根遍历森林中第一棵树的根结点的子树森林。森林。b.访问第一棵树的根结点。访问第一棵树的根结点。c.中根遍历除去第一棵树之后剩余的树构成中根遍历除去第一棵树之后剩余的树构成的森林。的森林。森林的森林的中根遍历中根遍历第 章 树 和 二 叉 树 若森林非空，则遍历方法为：若森林非空，则遍历方法为：a.后根遍历森林中第一棵树的根结点的子树森林。后根遍历森林中第
81、一棵树的根结点的子树森林。b.后根遍历除去第一棵树之后剩余的树构成的森林。后根遍历除去第一棵树之后剩余的树构成的森林。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 A第 章 树 和 二 叉 树 1234567后序遍历如下森林后序遍历如下森林所得序列为：所得序列为：DECBJIH7654321GA第 章 树 和 二 叉 树 6.5 6.5 哈夫曼树及其应用哈夫曼树及其应用 与哈夫曼树相关的基本概念与
82、哈夫曼树相关的基本概念与哈夫曼树相关的基本概念与哈夫曼树相关的基本概念 vv 路径和路径长度路径和路径长度路径和路径长度路径和路径长度 路径：路径：路径：路径：从一个结点到另一个结点之间的分支序列。从一个结点到另一个结点之间的分支序列。 路径长度路径长度路径长度路径长度：从一个结点到另一个结点所经过的分支数目。从一个结点到另一个结点所经过的分支数目。vv 结点的权和带权路径长度结点的权和带权路径长度结点的权和带权路径长度结点的权和带权路径长度 结点的权：结点的权：结点的权：结点的权：在实际的应用中，人们常常给树的每个结点赋予在实际的应用中，人们常常给树的每个结点赋予一个具有某种一个具有某种实际
83、意义的数值实际意义的数值实际意义的数值实际意义的数值，我们称该数值为这个结点的权。，我们称该数值为这个结点的权。 结点的带权路径长度：结点的带权路径长度：结点的带权路径长度：结点的带权路径长度：从树根到某一结点的路径长度与该结从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。点的权的乘积，叫做该结点的带权路径长度。 vv 树的带权路径长度树的带权路径长度树的带权路径长度树的带权路径长度 树的带权路径长度是指树中所有树的带权路径长度是指树中所有叶子叶子叶子叶子结点的带权路径长度结点的带权路径长度之之和和和和。第 章 树 和 二 叉 树 vv 树的带权路径长度树的带权路径长度
84、树的带权路径长度树的带权路径长度 树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径树的带权路径长度是指树中所有叶子结点的带权路径长度之和长度之和长度之和长度之和。 是由是由n n个带权叶子结点构成的所有二叉树中带权路径个带权叶子结点构成的所有二叉树中带权路径长度长度WPLWPL最小的二叉树。哈夫曼树又叫最佳判定树。最小的二叉树。哈夫曼树又叫最佳判定树。 vv 哈夫曼树哈夫曼树哈夫曼树哈夫曼树第 章 树 和 二 叉 树 例：有例：有例：有例：有4 4 4 4个结点，权值分别为个结点，权值分别为个结点，权值分
85、别为个结点，权值分别为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树步骤树步骤树步骤树步骤根据给定的根据给定的n n个权值个权值 w w1 1,w,w2 2,
86、,w wn n ，构造构造n n棵只有根结棵只有根结点的二叉树点的二叉树森林森林，令其权值为，令其权值为w wj j在森林中选取两棵根结点权值最小的树作左右子树，构在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森在森林中删除这两棵树，同时将新得到的二叉树加入森林中林中重复上述两步，直到只含一棵树为止，这棵树即为所求重复上述两步，直到只含一棵树为止，这棵树即为所求的哈夫曼树的哈夫曼树 构造构造构造构造HuffmanHuff
87、manHuffmanHuffman树的方法树的方法树的方法树的方法HuffmanHuffmanHuffmanHuffman算法算法算法算法第 章 树 和 二 叉 树 例例:a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118第 章 树 和 二 叉 树 例w=5,29,7,8,14,23,3,1151429 7823 3111429 7823 1135887151429233581111358191429238715113581929 231487152929148715291135819234211358192342291487152958113581923422
88、91487152958100第 章 树 和 二 叉 树 最佳判定树最佳判定树最佳判定树最佳判定树 例例例例: : : :学学学学生生生生成成成成绩绩绩绩的的的的分分分分布布布布呈呈呈呈正正正正态态态态分分分分布布布布即即即即：中中中中等等等等成成成成绩绩绩绩的的的的学学学学生生生生较较较较多多多多，而而而而较较较较好好好好或或或或较较较较差差差差学学学学生生生生均均均均比比比比较较较较少少少少。设其分布规律如下表：设其分布规律如下表：设其分布规律如下表：设其分布规律如下表： 等级分数段比例优秀良好中等及格不及格05960697079 8089 90100515403010哈夫曼树的应用哈夫曼树
89、的应用第 章 树 和 二 叉 树 要编制一个将百分制转换成五级分制（优、良、中、及、不要编制一个将百分制转换成五级分制（优、良、中、及、不及）的程序。显然这程序很简单。如下：及）的程序。显然这程序很简单。如下：if(a60)thenprintf(“不及格不及格”);elseif(a70)thenprintf(“及格及格”);elseif(a80)thenprintf(“中等中等”);elseif(a90)thenprintf(“良好良好”);elseprintf(“优秀优秀”);第 章 树 和 二 叉 树 上边的判定过程用下面的图上边的判定过程用下面的图(a)可以表示可以表示:(a)由此可知由
90、此可知由此可知由此可知: : : :若采若采若采若采用图（用图（用图（用图（a a a a）来进）来进）来进）来进行判断，则行判断，则行判断，则行判断，则80%80%80%80%以上的数据要进以上的数据要进以上的数据要进以上的数据要进行三次或三次以行三次或三次以行三次或三次以行三次或三次以上的比较才能得上的比较才能得上的比较才能得上的比较才能得到结果。到结果。到结果。到结果。第 章 树 和 二 叉 树 而而而而如如如如果果果果我我我我们们们们以以以以各各各各分分分分数数数数段段段段人人人人数数数数占占占占总总总总人人人人数数数数的的的的比比比比例例例例5 5 5 5、15151515、4040
91、4040、30303030、10101010为为为为权权权权值值值值构构构构造造造造哈哈哈哈夫夫夫夫曼曼曼曼树树树树，可可可可得得得得到到到到（b b b b）所所所所示示示示的的的的判判判判定定定定树树树树, , , ,用用用用这这这这个个个个判判判判定定定定树树树树进进进进行行行行判判判判断断断断可可可可以以以以使使使使大大大大部部部部分分分分数数数数据据据据经经经经过过过过较较较较少少少少次次次次数数数数的的的的比较得到结果。比较得到结果。比较得到结果。比较得到结果。 Y(b)第 章 树 和 二 叉 树 在在传传送送电电文文时时，希希望望总总长长尽尽可可能能地地短短。如如对对每每个个字字
92、符符（上上边边是是四四个个字字符符ABCD）设设计计长长度度不不等等的的编编码码，且且让让在在电电文文中中出出现现次次数数较较多多的的字字符符采采用用尽尽可可能能短短的的编编码码，则则电电文文的的总总长长便便可可减少。减少。第 章 树 和 二 叉 树 在上面，如果设计在上面，如果设计ABCD的编码分别的编码分别为为0，00，1，01，则上述的九个字符的电，则上述的九个字符的电文可转换成总长为文可转换成总长为11的字符串的字符串“00010111000”，但是这样的电文无法翻，但是这样的电文无法翻译，如传送过去的前三个字符的子串译，如传送过去的前三个字符的子串“000”就可有几种译法，或是就可有
93、几种译法，或是AB或是或是AAA或是或是BA。故要设计长短不等的编码，。故要设计长短不等的编码，则必须是则必须是任一个字符的编码都不是另一个任一个字符的编码都不是另一个字符的编码的前缀字符的编码的前缀，这种编码称为前缀编，这种编码称为前缀编码。码。第 章 树 和 二 叉 树 如何得到使电文总长最短的二进前缀编码呢？如何得到使电文总长最短的二进前缀编码呢？假设每种字符在电文中出现的次数为假设每种字符在电文中出现的次数为wk，其编码长度为，其编码长度为lk，电文中只有，电文中只有n种字符，则电文总长为种字符，则电文总长为:对应到二叉树上，若置对应到二叉树上，若置Wk为叶子结点的权，为叶子结点的权，
94、lk恰为从根到恰为从根到叶子的路径长度。则叶子的路径长度。则上式恰为二叉树上带权路径长度上式恰为二叉树上带权路径长度。由此。由此可见，设计电文总长最短的二进制前缀编码，就是以可见，设计电文总长最短的二进制前缀编码，就是以n种字符种字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二出现的频率作权，设计一棵哈夫曼树的问题，由此得到的二进制前缀编码便称为哈夫曼编码。进制前缀编码便称为哈夫曼编码。第 章 树 和 二 叉 树 利用利用哈夫曼算法哈夫曼算法可以设计出可以设计出最优的前缀最优的前缀编码编码。假设有一棵如下图的二叉树，其四个。假设有一棵如下图的二叉树，其四个叶结点分别表示叶结点分别表示A
95、 A，B B，C C，D D四个字符。且四个字符。且约约定：左分支表示字符定：左分支表示字符“1 1”右分支表示字符右分支表示字符“0 0”，则对每个叶结点有唯一的一条从根，则对每个叶结点有唯一的一条从根结点出发的路径，这样从根到叶路径上的分结点出发的路径，这样从根到叶路径上的分支字符组成的字符串作为该叶结点的编码支字符组成的字符串作为该叶结点的编码（二进制编码）（二进制编码）第 章 树 和 二 叉 树 哈夫曼编码算法的实现哈夫曼编码算法的实现 由于哈夫曼树中没有度为由于哈夫曼树中没有度为1 1的的结点，一棵有结点，一棵有n n个叶子结点的哈夫个叶子结点的哈夫曼树共有曼树共有2n-1个结点，可
96、以用一个结点，可以用一大小为大小为2n-12n-1的向量表示。的向量表示。第 章 树 和 二 叉 树 由于在构成哈夫曼树之后，由于在构成哈夫曼树之后，为求为求编码编码需从叶子结点出发走一条叶子到需从叶子结点出发走一条叶子到根的路径，而根的路径，而为译码为译码需从根出发走一需从根出发走一条从根到叶子的路径。这样对每个结条从根到叶子的路径。这样对每个结点而言，即需知双亲的信息，又需知点而言，即需知双亲的信息，又需知孩子结点的信息，为此设定下述存储孩子结点的信息，为此设定下述存储结构。结构。如何选定结点结构？如何选定结点结构？第 章 树 和 二 叉 树 typedef typedef struct
97、Nodestruct Node int weight;int weight;/权值权值int parent,LChild,RChild;int parent,LChild,RChild;/双亲和左右孩子双亲和左右孩子 HTNode, *HTree; HTNode, *HTree;typedef char *HuffmanCode;typedef char *HuffmanCode;数据类型的定义如下：数据类型的定义如下：LChildLChild weightweight parentparent RChildRChild第 章 树 和 二 叉 树 创建哈夫曼建哈夫曼树并求哈夫曼并求哈夫曼编码的
98、算法如下：的算法如下：viod CreatHTree(viod CreatHTree(HTree ht , HuffmanCode hc,int *w, int nHTree ht , HuffmanCode hc,int *w, int n) ) /*w/*w存放存放n n个权值个权值, ,构造哈夫曼树构造哈夫曼树ht,ht,并求出哈夫曼编码并求出哈夫曼编码hc */hc */ int start,c,p; int start,c,p; m=2*n-1; m=2*n-1; /*/*叶子结点总数叶子结点总数n*/n*/ ht=(HTree)malloc(m+1)*sizeof(HTNode);
99、 ht=(HTree)malloc(m+1)*sizeof(HTNode); for(i=1;i=n;i+) for(i=1;i=n;i+) hti = wi,0,0,0; hti = wi,0,0,0; for(i=n+1;i=m;i+) for(i=n+1;i=m;i+) hti =0,0,0,0; hti =0,0,0,0;/* /* 初始化初始化* */ /第 章 树 和 二 叉 树 for(i=n+1;i=m;i+)select(ht,i-1,&s1,&s2);/*在在ht1hti-1的范围内选择两个的范围内选择两个parent为为0且且weight最小的结点，其序号分别赋值给最小的
100、结点，其序号分别赋值给s1、s2返回，返回，select函数要求在上机调试时补充定义函数要求在上机调试时补充定义*/hts1.parent=i;hts2.parent=i;hti.LChild=s1;hti.RChild=s2;hti.weight=hts1.weight+hts2.weight;/*哈夫曼树建立完毕哈夫曼树建立完毕*/第 章 树 和 二 叉 树 / /* *以下程序是从叶子结点到根，以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程逆向求每个叶子结点对应的哈夫曼编码的过程* */ /hc=(Huffmancode)malloc(n+1)*sizeof(char
101、*);/申请字符指针数组空间申请字符指针数组空间cd=(char*)malloc(n*sizeof(char);/申请字符数组空间申请字符数组空间cdn-10；/*为将来整体处理字串方便为将来整体处理字串方便*/for(i=1;i1)n(n1)n(n1)n(n1)个结点的二叉树可以看成是由个结点的二叉树可以看成是由个结点的二叉树可以看成是由个结点的二叉树可以看成是由一个根结点、一棵具有一个根结点、一棵具有一个根结点、一棵具有一个根结点、一棵具有i i i i个结点的左子树、和一棵具有个结点的左子树、和一棵具有个结点的左子树、和一棵具有个结点的左子树、和一棵具有n-i-1n-i-1n-i-1n-
102、i-1个结点的右子树组成的，如图个结点的右子树组成的，如图个结点的右子树组成的，如图个结点的右子树组成的，如图6.286.286.286.28所示，其中所示，其中所示，其中所示，其中0in-10in-10in-10in-1。 第 章 树 和 二 叉 树 由此可得出如下递推公式：由此可得出如下递推公式：由此可得出如下递推公式：由此可得出如下递推公式： 由上式可知：由上式可知：当当n n3 3时，时，b b3 3b b0 0*b*b2 2 +b +b1 1* b* b1 1 +b +b2 2* b* b0 0=5 =5 恰好同上面采恰好同上面采用观察方法得到的结果相同。用观察方法得到的结果相同。 第 章 树 和 二 叉 树 由二叉树的计数可推得树的计数。由由二叉树的计数可推得树的计数。由“森林与二叉树的转换森林与二叉树的转换”中可知一棵树可转换成唯一的一棵没有右子树的二叉树，中可知一棵树可转换成唯一的一棵没有右子树的二叉树，反之亦然。则具有反之亦然。则具有n n个结点有不同形态的树的数目个结点有不同形态的树的数目t tn n 和具有和具有n-1n-1个结点互不相似的二叉树的数目相同。即个结点互不相似的二叉树的数目相同。即t tn n=b=bn-1 n-1 。下图展。下图展示了具有示了具有4 4个结点的树和具有个结点的树和具有3 3个结点的二叉树的关系。个结点的二叉树的关系。
