(6.5.1)--ch6-5树和森林0821.pdf

《(6.5.1)--ch6-5树和森林0821.pdf》由会员分享，可在线阅读，更多相关《(6.5.1)--ch6-5树和森林0821.pdf（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、Data Structures and AlgorithmsTrees and Forest 2数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees and Forest1.The storage structure of general trees2.The transformation of trees,forest and binary trees3.The traversal of trees and forestsABCDGEF3parentdataSerial number0123456A-1B0C0D1E1F1G2数据结构与算法数据结构与算法

2、第第 六六 章章 树和二叉树树和二叉树 1.1 Parental representationdataparent1.The storage structure of a tree6.5 Trees and Forest40123456ABCDEFG12 345 6 Each node establishes:Child linked list 数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 1.2 Child representation1.The storage structure of a tree6.5 Trees and ForestABCDGEF5data n

3、ext sibling nodefirst child nodeABDCEFGBinary linked list of trees数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 1.3 Child sibling representation1.The storage structure of a tree6.5 Trees and ForestABCDGEF6 Both tree and binary tree can use binary linked list as storage structure,then the corresponding transfor

4、mation relationship between tree and binary tree can be derived by binary linked list.Attention:the binary tree transformed from tree,its concept of left and right subtree change to:left for the child,right for the sibling.数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 2.The transformations between trees,forest

5、,and binary trees6.5 Trees and ForestABCDEFGABCDEFGno siblingno right child Sibling trees in the forest will be converted to the right subtree.Tree and binary tree correspond:tree binary tree 数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees and Forest7 root root first child left child next sibling right

6、 child8ABCDGEFH.Add lines:Add lines between all the siblings;数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees and ForestTree converted to binary tree9ABCDGEFH.Delete lines:for each node,except for the line between the first child and itself,the lines connected to the rest children are deleted;数据结构与算法数据结

7、构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees and ForestTree converted to binary treeGABCDEFH10ABCDGEFH.Rotate:With the root node as the axis,the whole tree is rotated clockwise at a certain angle to make the structure clear and the left and right subtrees are clear.数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees

8、 and ForestTree converted to binary tree.Add lines:add lines between siblings;(the root nodes of each tree as siblings)11数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABCDGHIJEF6.5 Trees and ForestForest converted to binary tree12数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABCDGHIJEF6.5 Trees and ForestForest converted

9、 to binary tree.Delete lines:keep the line between each node and its first child,delete lines between node and other children;13数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABCDGHIJEF6.5 Trees and ForestForest converted to binary tree.Rotate:Take the root node of the first binary tree as the axis,rotate the w

10、hole tree clockwise at a certain angle to make the structure clear and the left and right subtrees clear.ABDCEFHIJG14The root node of a binary tree without right children is transformed into a tree.The root node of a binary tree by a right child is transformed into a forest.数据结构与算法数据结构与算法 第第 六六 章章 树

11、和二叉树树和二叉树 Binary trees converted to forests6.5 Trees and Forest15ABEDHCFG数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 .Add lines:If a node i is the left child of its parent p,then the right child j of i and the right child k of j.along the right chain to the lowest right end are connected with the node p;6.5

12、Trees and Forest16ABEDHCFG数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 .Delete lines:Delete the connection between parents and right child in the original binary tree;6.5 Trees and Forest17ABEDHCFGABDCEGFH数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 .Rotate:The whole tree is rotated and adjusted to make its structure c

13、lear and the left and right subtrees are clear.6.5 Trees and Forest18数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABDCEFHIJG.Add lines6.5 Trees and Forest19数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABDCEFHIJG.Add lines.Delete lines6.5 Trees and Forest20ABCDGHIJEF数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 ABDCEFHIJG.Add lines.Delete lines.Rotate6.5 Trees and Forest21数据结构与算法数据结构与算法 第第 六六 章章 树和二叉树树和二叉树 6.5 Trees and Forest1.The storage structure of a tree2.The transformation of trees,forest and binary trees3.The traversal of trees and forests Thanks