63树的存储结构 根据数据元素之间关系的不同表示方式,常用的 树存储结构主要有三种:双亲表示法、孩子表示法和 孩子兄弟表示法。 631双亲表示法 在树中,除根结点没有双亲外,其他每个结点的双 亲是唯一确定的。因此,根据树的这种性质,存储树 中结点时,可以包含两个信息:结点的值data和体现 结点之间相互关系的属性该结点的双亲 parent。借 助于每个结点的这两个信息便可唯一地表示任何一棵 树。这种表示方法称为双亲表示法
6.3 树的存储结构 根据数据元素之间关系的不同表示方式，常用的 树存储结构主要有三种：双亲表示法、孩子表示法和 孩子兄弟表示法。 6.3.1 双亲表示法 在树中，除根结点没有双亲外，其他每个结点的双 亲是唯一确定的。因此，根据树的这种性质，存储树 中结点时，可以包含两个信息：结点的值data和体现 结点之间相互关系的属性__该结点的双亲parent。借 助于每个结点的这两个信息便可唯一地表示任何一棵 树。这种表示方法称为双亲表示法
#define maXsize 100 typedef char datatype;/*结点值的类型*/ typedef struct node/结点的类型* datatype data int parent;/结点双亲的下标* f node typedef struct tree node treelist[MAXSIZE]/存放结点的数组 int length,root;/树中实际所含结点的 个数及根结点的位置* f tree:
#define MAXSIZE 100 typedef char datatype; /*结点值的类型*/ typedef struct node /*结点的类型*/ { datatype data; int parent; /*结点双亲的下标*/ } node; typedef struct tree { node treelist[MAXSIZE];/*存放结点的数组*/ int length, root ; /* 树中实际所含结点的 个数及根结点的位置*/ } tree;
dataparent ←root A B B DEFGH I(JK 6789 (a)一棵树 6-6-6 10 K (b)(a)图的双亲表示法 图64
B C D E F G A H I J K data parent A -1 B 0 C 0 D 0 E 1 F 1 G 3 H 3 I 6 J 6 K 6 0 1 2 3 4 5 6 7 8 9 10 root (a) 一棵树 (b) (a)图的双亲表示法 图6 .4
632孩子表示法 采用孩子表示法表示一棵树时,树中每个结点除 了存储其自身的值之外,还必须指出其所听有子女的位 置,即整棵树中所有结点的相互关系是通过指明结点 子女的位置来体现的,称这种表示法为孩子表示法。 根据子女位置的实现方法不同,孩子表示法分为三种: 指针方式的孩子表示法、数组方式的孩子表示法、 链表方式的孩子表示法
6.3.2 孩子表示法 采用孩子表示法表示一棵树时，树中每个结点除 了存储其自身的值之外，还必须指出其所有子女的位 置，即整棵树中所有结点的相互关系是通过指明结点 子女的位置来体现的，称这种表示法为孩子表示法。 根据子女位置的实现方法不同，孩子表示法分为三种： 指针方式的孩子表示法 、数组方式的孩子表示法、 链表方式的孩子表示法