《数据结构》 第六章下)
《 数据结构》 第六章(下)
数据结构 64树和森林 641树的存储结构 双亲表示法 实现:定义数组存放树的结点,每个结点含两个域: 数据城:存放结点本身信息。 双亲域:指示本结点的双亲结点在数组中的位置。 特点:找双亲容易,找孩子难。 静态双亲链表的类型定义参见P135
数据结构 tjm 静态双亲链表的类型定义参见P135 6.4 树和森林 6.4.1 树的存储结构 双亲表示法 实现：定义数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息。 双亲域：指示本结点的双亲结点在数组中的位置。 特点：找双亲容易，找孩子难
数据结构 data parent 0 b abc e f g h 45678 efgh 2444
数据结构 tjm a b c d e f g h i － 1 01124440 acdefghib data parent 501234678
数据结构 孩子链表表示法(类型定义参见P136 每个结点的孩子结点用单链表存储,再用含n个 元素的数组指向每个孩子链表。 data fc a 0 2∧ 4∧ 5 d 7 g 2345678 abcdefg
数据结构 tjm a b c d e f g h i 1 2 ^ 3 4 ^ 6 7 8 ^ 5 ^ 5 0 1 2 3 4 6 7 8 a c d e f g h i b ^ ^ ^ ^ ^ data fc 孩子链表表示法（类型定义参见P136） 每个结点的孩子结点用单链表存储，再用含n个 元素的数组指向每个孩子链表
数据结构 带双亲的孩子链表 data parent fc abc 24 00 3d1 1356 7 efgh 2444 ∧∧
数据结构 tjm 5 0 1 2 3 4 6 7 8 a c d e f g h i b data fc 1 2 3 4 6 7 8 5 ^ ^ ^ ^ ^ ^ ^ ^ ^ －1 0 1 1 2 4 4 4 0 parent a b c d e f g h i 带双亲的孩子链表
数据结构 孩子兄弟表示法(二叉树表示法) 实现:用二叉链表作树的存储 结构,链表中每个结点的两个a 指针域分别指向其第一个孩子 结点和下一个兄弟结点。 al A de卧f g囗囚山区
数据结构 tjm a b c d e f g h i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储 结构，链表中每个结点的两个 指针域分别指向其第一个孩子 结点和下一个兄弟结点
数据结构 642森林与二叉树的转换 树 二叉树 A (B)(C D ABCDE B D E A B B+c E D
数据结构 tjm A B C E D 树 A B C D E 二叉树 A ^ ^ B C ^ D ^ ^ E ^ A ^ ^ B C ^ D ^ ^ E ^ 6.4.2 森林与二叉树的转换 A ^ ^ B C ^ D ^ ^ E ^
将肉转换成二叉树 数据结构 加线:在兄弟之间加一连线。 抹线:对每个结点,除了其左孩子外,抹掉其与 其余孩子之间的连线。 旋转:将树作适当的旋转即可 ⑥⑩⊙⑥⑥画① 树转换成的二叉树其右子树一定为空。 ①m
数据结构 tjm A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H 树转换成的二叉树其右子树一定为空。 I 加线：在兄弟之间加一连线。 抹线：对每个结点，除了其左孩子外，抹掉其与 其余孩子之间的连线。 旋转：将树作适当的旋转即可。 将树转换成二叉树
数据结构 二叉树转换成树 加线:若某结点是双亲结点的左孩子,则将该结点 的右孩子,右孩子的右孩子,…沿分支找到的所 有右孩子,都与该结点的双亲用线连起来。 抹线:抹掉原二叉树中双亲与右孩子之间的连线。 调整:将结点按层次排列,形成树结构
数据结构 tjm A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I A B C D E F G H I 将二叉树转换成树 加线：若某结点是双亲结点的左孩子，则将该结点 的右孩子，右孩子的右孩子，……沿分支找到的所 有右孩子，都与该结点的双亲用线连起来。 抹线：抹掉原二叉树中双亲与右孩子之间的连线。 调整：将结点按层次排列，形成树结构
数据结构 转换成二叉树 将各棵树分别转换成二叉树。 将每棵树的根结点用线相连。 以第一棵树根结点为二叉树的根,再以根结点为 轴心,顺时针旋转,构成二叉树型结构。 ⑦ →◎
数据结构 tjm A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J A B C D E F G H I J 森林转换成二叉树 将各棵树分别转换成二叉树。 将每棵树的根结点用线相连。 以第一棵树根结点为二叉树的根，再以根结点为 轴心，顺时针旋转，构成二叉树型结构