《数据结构》课程PPT教学课件（2015）第6章 树和二叉树（下）

《数据结构》 第六章树和二叉树（下）

《 数据结构》 第六章 树和二叉树 (下)

数据结构 6.4 树和森林 6.4.1树的存储结构 双亲表示法 实现：定义数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息。 双亲域：指标本结点的双亲结点在数组中的位置。 特点：找双亲容易，找孩子难。 静态双亲链表的类型定义参见P135 tjm

数据结构 tjm 静态双亲链表的类型定义参见P135 6.4 树和森林 6.4.1 树的存储结构 双亲表示法 实现：定义数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息。 双亲域：指示本结点的双亲结点在数组中的位置。 特点：找双亲容易，找孩子难

数据结构 data parent 日 0 a 1 b 0 b 2 c 0 e 3 d 4 e 5 f 2 g h 6 g 4 7 h 4 8 1 4

数据结构 tjm a b c d e f g h i － 1 01124440 acdefghib data parent 501234678

数据结构 孩子链表表示法（类型定义参见P136) 每个结点的孩子结点用单链表存储，再用含个 元素的数组指向每个孩子链表。 data fc a a b C 1 b 2 5 d e 3 d 4 e 6 8 g h 5 f A 6 g A 7 h 8 1 A tjm

数据结构 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个 元素的数组指向每个孩子链表

数据结构 带双亲的孩子链表 a data parent fc 0 a -1 1 b 0 2 c 0 3 d 1 4 e 1 8^ 5 2 N 6 8 4 7 h 4 8i 4

数据结构 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 指针域分别指向其第一个孩子 b 结点和下一个兄弟结点。 Q a d e A 7 h-

数据结构 tjm a b c d e f g h i a b c d e f g h i ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 孩子兄弟表示法（二叉树表示法） 实现：用二叉链表作树的存储 结构，链表中每个结点的两个 指针域分别指向其第一个孩子 结点和下一个兄弟结点

数据结构 6.4.2 森林与二叉树的转换 树 二叉树 A A B E B D D E A A B B E D D E

数据结构 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 ^

将树转换成二叉树 数据结构 加线：在兄弟之间加一连线。 抹线：对每个结点，除了其左孩子外，抹掉其与 其余孩子之间的连线。 旋转：将树作适当的旋转即可。 B B F 树转换成的二叉树其右子树一定为空

数据结构 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 森林转换成二叉树 将各棵树分别转换成二叉树。 将每棵树的根结点用线相连。 以第一棵树根结点为二叉树的根，再以根结点为 轴心，顺时针旋转，构成二叉树型结构