§5.3树的存储结构 ★树的存储结构 今双亲表示法 实现:定义结构数组存放树的结点,每个结点含两个域 ◆数据域:存放结点本身信息 ◆双亲域:指示本结点的双亲结点在数组中位置 ●特点:找双亲容易,找孩子难 typedef struct node i datatype data Int parent JD Jd tIM
§5.3 树的存储结构 树的存储结构 ❖双亲表示法 ⚫实现：定义结构数组存放树的结点，每个结点含两个域： ◆数据域：存放结点本身信息 ◆双亲域：指示本结点的双亲结点在数组中位置 ⚫特点：找双亲容易，找孩子难 typedef struct node { datatype data; int parent; }JD; JD t[M];
0号单元不用或 存结点个数 data parent 0 0 0 f g 23456789 abcd e f gh 223555 如何找孩子结点
a b c d e f g h i acdefghib 012235551 0 9 6012345789 data parent 0号单元不用或 存结点个数 如何找孩子结点
今孩子表示法 多重链表:每个结点有多个指针域,分别指向其子树的根 ◆结点同构:结点的指针个数相等,为树的度D ◆结点不同构:结点指针个数不等,为该结点的度d data child 1 child2 childD data degree child 1 child2 childd 孩子链表:每个结点的孩子结点用单链表存储,再用含n个 元素的结构数组指向每个孩子链表 孩子结点: typedef struct node int child;∥该结点在表头数组中下标 struct node*next;∥指向下一孩子结点 表头结点: typedef struct tnode datatype data,∥数据域 struct node*fe;∥指向第一个孩子结点 TD TDt[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]不用
b da fc d 2 g 23456789 abcdefgh 7 8 如何找双亲结点
a b c d e f g h i 6012345789 acdefghib data fc 2 3 ^ 4 5 ^ ^ 7 8 9 ^ 6 ^ ^^^ 如何找双亲结点 ^
0带双亲的孩子链表 data parent fc a abc 246 g)(h①4d e 7 6f 789 h 223555
⚫带双亲的孩子链表 612345789 acdefghib data fc 2 3 4 5 7 8 9 6 ^^ ^ ^ ^ ^^^^ 012235551 parent a b c d e f g h i