ds树的存储与转换.pptVIP

* 6.4 树和森林 一、树的存储结构 二、森林与二叉树的转换 1、双亲表示法 2、孩子表示法 3、树的二叉链表(孩子-兄弟） 表示法 一、树的存储结构 A B C D E F G 0 A -1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 r = 0 n = 6 数组下标 data parent 1、双亲表示法: 以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点的位置。 typedef struct PTNode { Elem data; int parent; // 双亲位置域 } PTNode; data parent #define MAX_TREE_SIZE 100 结点结构: C语言的类型描述: typedef struct { PTNode nodes[MAX_TREE_SIZE]; int r, n; // 根结点的位置和结点个数 } PTree; 树结构: 这种存储结构利用了每个结点（除根外）只有唯一双亲的性质。PARENT(T,x)操作可在常量时间内实现。反复调用PARENT操作，直到遇见无双亲的结点时，便找到了树的根，这就是ROOT(x)操作的执行过程。 但是，在这种表示法中，求结点的孩子时需要遍历整个结构。 由于树中每个结点可能有多棵子树，则在采用链式存储结构时可用多重链表，即每个结点有多个指针域，其中，每个指针指向一棵子树的根结点。此时，链表中的结点可有如下两种结点格式： data child1 child2 … childd data child1 child2 … Childd degree 2、孩子表示法: 若采用第一种结点格式，则多重链表中的结点是同构的，其中d为树的度。由于树中很多结点的度小于d，所以链表中有很多空链域，空间较浪费。不难推出，在一棵有n个结点度为k的树中必有n(k-1)+1个空链域。 若采用第二种结点格式，则多重链表中的结点是不同构的，其中d 为结点的度，degree域的值同d。此时，虽能节省存储空间，但操作不方便。 另一种办法是把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空表）。而n个头指针又组成一个线性表，为了便于查找，可采用顺序存储结构。 孩子链表表示法: A B C D E F G 0 A 1 B 2 C 3 D 4 E 5 F 6 G r=0 n=6 data firstchild 1 2 3 4 5 6 typedef struct CTNode { int child; struct CTNode *next; } *ChildPtr; 孩子结点结构: child next C语言的类型描述: typedef struct { Elem data; ChildPtr firstchild; //孩子链的头指针 } CTBox; 双亲结点结构： data firstchild typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r； // 结点数和根结点的位置 } CTree; 树结构: 与双亲表示法相反，孩子表示法便于那些涉及孩子的操作的实现，却不适用于PARTEN(x)操作。可把双亲表示法和孩子链表合在一起，组成带双亲的孩子链表。 A B C D E F G 0 A 1 B 2 C 3 D 4 E 5 F 6 G r=0 n=6 data parent firstchild 1 2 3 4 5 6 -1 0 0 0 2 2 4 带双亲的孩子链表 又称二叉树表示法，或二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。 3、树的二叉链表 (孩子-兄弟) 存储表示法 typedef struct CSNode{