6.4树和森林 6.4.1树的存储结构 双亲表示法(顺序存储) / 树的双亲表存储表示 #define MAX TREE SIZE 100 typedef struct PTNode i TElem Type data Int parent;∥双亲位置域 SPTNode typedef struct PTNode nodes[MAX TREE SiZe int n ∥结点数 SPRee
6．4 树和森林 6.4.1树的存储结构 一、双亲表示法（顺序存储） //-----------树的双亲表存储表示----------// #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int parent; //双亲位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }PTree;
双亲表示法举例 数组下标:0 R|-1 R A B 0—00 D E F 23456 A—B—C—DE—F G)(H(K 7G|6 *便于涉及双亲的操作; 8H6 *求结点的孩子时需要遍历整棵树 9K6
双亲表示法举例 R A D E F C B G H K R -1 A 0 B 0 C 0 D 1 E 1 F 3 G 6 H 6 K 6 0 1 2 3 4 5 6 7 8 9 数组下标: * 便于涉及双亲的操作； * 求结点的孩子时需要遍历整棵树
6.4.1树的存储结构 二、孩子表示法(顺序存储) #define MAX TREE SIZE 100 typedef struct PTNode i TElem Type data int child 1;∥第1个孩子位置域 int child2 ∥第2个孩子位置域 int childd ∥第d个孩子位置域 I PTNode typedef struct PTNode nodes MAX TREE SIZe Int n 结点数 )PTree
6.4.1树的存储结构 二、孩子表示法（顺序存储） #define MAX_TREE_SIZE 100 typedef struct PTNode { TElemType data; int child1; //第1个孩子位置域 int child2; //第2个孩子位置域 ...... int childd; //第d个孩子位置域 }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; //结点数 }PTree;
孩子表示法举例 R 数组下标:0R123 1A450 A 2B000 B C600 D E D000 E000 F789 G(HK 34567 G000 便于涉及孩子的操作:求双亲不方便:8H000 *采用同构的结点,空间浪费 K000
孩子表示法举例 R A D E F C B G H K 0 1 2 3 4 5 6 7 8 9 数组下标: * 便于涉及孩子的操作；求双亲不方便； * 采用同构的结点，空间浪费。 R 1 A 4 B 0 C 6 D 0 E 0 F 7 G 0 H 0 K 0 2 3 5 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0
孩子链表存储表示(链式存储) typedef struct CTNode{∥孩子结点 In child struct CTNode *next )*ChildPtr typedef struct i TElem Type data ChildPtr firstchild;∥孩子链表头指针 ICTBOX typedef struct i CTBox nodes[MAX TREE SIZe nt n.r. ∥结点数和根的位置 OCTree
孩子链表存储表示（链式存储） typedef struct CTNode{ //孩子结点 int child; struct CTNode *next; } *ChildPtr; typedef struct { TElemType data; ChildPtr firstchild; //孩子链表头指针 }CTBox; typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; //结点数和根的位置 }CTree;