数据结构第4章树.ppt

2、将一个森林转换为二叉树 转换方法： ①树转换为二叉树：将森林中的每棵树转换为二叉树； ②连接根结点：再将各二叉树的根结点视为兄弟从左至右连在一起； ③调整：按树的层次进行调整，将原来的右兄弟变成其右孩子，原来的无兄弟结点变成左孩子。 3、二叉树到树、森林的转换 转换方法： ①加线：在左孩子结点的双亲与左孩子结点的右孩子、右孩子的右孩子等等之间加一连线； ②去线：去掉所有双亲与右孩子之间的连线； ③调整：按树的层次进行调整，将原来根结点的右孩子、右孩子的右孩子等等变成森林中树的根，其它结点的右孩子、右孩子的右孩子等等变成兄弟。 33 33 33 例如：图(a)的森林转换为二叉树的过程 (a) 第一步 各树转换为二叉树 第二步 连接根结点 第三步 调整 A B E G H D C I F A B D C F E K J G H I K J A B D C F E G H I K J A B D C F E H I K J G 例如：图(a)的二叉树转换为树、森林的过程 (a) 第一步 加线 第二步 去线 第三步 调整 A B E G H D C I F A B E G H D C I F A B E G H D C I F A B E G H D C I F 例如：图(a)的二叉树转换为树、森林的过程 (a) 第一步 连线 第二步 去线 第三步 调整 A B E G H D C I F K J A B D C F E H I K J G A B D C F E H I K J G A B D C F E H I K J G 二、树的存储结构 1、双亲链表表示法 ??? 　该表示法用向量表示结点，并用一个整型量parent指示其双亲的位置，称为指向其双亲的指针。 双亲链表向量表示的描述#define MaxTreeSize 100 //定义向量空间的容量 typedef char DataType； //定义结点数据域类型typedef struct{ //定义结点 ?????DataType data；//定义结点数据域 ????? int parent； //双亲指针，指示双亲的位置??? }PTreeNode；typedef struct{//定义链表 ????? PTreeNode nodes[MaxTreeSize];????? int n； //结点总数???? }PTree；PTree T； //T是双亲链表注意：若T.nodes[i].parent=j，则T.nodes[i]的双亲是T.nodes[j]。 例如：图(a)的树的双亲链表表示为： (a) 图(a)的树的双亲链表T 说明：根结点A无双亲,所以parent值为-1,H和I的parent值为3,表示它们的双亲为下标为3的结点D。双亲链表表示法适合求指定结点的双亲或祖先(包括根)；求指定结点的孩子或其它后代时，可能要遍历整个数组。 A B E G H D C I F … 3 3 1 1 1 0 0 0 -1 … I H G F E D C B A data parent 0 1 3 2 4 5 6 7 8 MaxTreeSize-1 下标 2、孩子链表表示法 ??? 　该表示法为树中每个结点设置一个孩子链表，并将这些结点及相应的孩子链表的头指针存放在一个向量中。 孩子链表表示的描述#define MaxTreeSize 100 //定义向量空间的容量 typedef char DataType； //定义结点数据域类型