§5.3树的存储结构 ★树的存储结构 冬双亲表示法 ●实现：定义结构数组存放树的结点，每个结点含两个域： ◆数据域：存放结点本身信息 ◆双亲域：指示本结点的双亲结点在数组中位置 ●特点：找双亲容易，找孩子难 typedef struct node datatype data; int parent; JD: JD t[M];
§5.3 树的存储结构 树的存储结构 ❖双亲表示法 ⚫实现：定义结构数组存放树的结点，每个结点含两个域： ◆数据域：存放结点本身信息 ◆双亲域：指示本结点的双亲结点在数组中位置 ⚫特点：找双亲容易，找孩子难 typedef struct node { datatype data; int parent; }JD; JD t[M];
0号单元不用或 存结点个数 data parent b 0 0 9 d 1 a 0 2 b c g 3 4 d 2 5 e 2 6 f 3 7 g 5 8 h 5 如何找孩子结点、 9 5
a b c d e f g h i acdefghib 012235551 0 9 6012345789 data parent 0号单元不用或 存结点个数 如何找孩子结点
孩子表示法 ●多重链表：每个结点有多个指针域，分别指向其子树的根 ◆结点同构：结点的指针个数相等，为树的度D ◆结点不同构：结点指针个数不等，为该结点的度d data child1 child2 childD data degree child1 child2 childd ●孩子链表：每个结点的孩子结点用单链表存储，再用含个 元素的结构数组指向每个孩子链表 孩子结点：typedef struct node {int child;/该结点在表头数组中下标 struct node*next;/指向下一孩子结点 JD; 表头结点： typedef struct tnode datatype data; /数据域 struct node *fc: /指向第一个孩子结点 TD; TD t[M]; /[0]不用
❖孩子表示法 ⚫多重链表：每个结点有多个指针域，分别指向其子树的根 ◆结点同构：结点的指针个数相等，为树的度D ◆结点不同构：结点指针个数不等，为该结点的度d data child1 child2 . childD data degree child1 child2 . childd ⚫孩子链表：每个结点的孩子结点用单链表存储，再用含n个 元素的结构数组指向每个孩子链表 孩子结点：typedef struct node { int child; //该结点在表头数组中下标 struct node *next; //指向下一孩子结点 }JD; 表头结点：typedef struct tnode { datatype data; //数据域 struct node *fc; //指向第一个孩子结点 }TD; TD t[M]; //t[0]不用
a b data fc d e a 2 3 g h 2 b 4 5 3 6 4 d 5 7 48 9 6 f A 7 g 8 h 如何找双亲结点3 9
a b c d e f g h i 6012345789 acdefghib data fc 2 3 ^ 4 5 ^ ^ 7 8 9 ^ 6 ^ ^^^ 如何找双亲结点 ^
●带双亲的孩子链表 2 data parent fc 1 0 2 3 b 日 2 b 1 4 5 d 3 g h 4 d 2 5 e 2 7 8 6 3 7 g 5 8 h 5 9 i 5 7
⚫带双亲的孩子链表 612345789 acdefghib data fc 2 3 4 5 7 8 9 6 ^^ ^ ^ ^ ^^^^ 012235551 parent a b c d e f g h i