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;
孩子链表存储表示举例 T nodes[ 1: T n=10; Tr=0 数组下标:0R R 十2-13 A 5 2B|/ A B( 3C 4D D E F 6F 7 G)(H)(K)7G| *便于涉及孩子的操作 8 H 求结点的双亲时不方便。9K
孩子链表存储表示举例 R A D E F B C G H K 0 1 2 3 4 5 6 7 8 9 数组下标: * 便于涉及孩子的操作； * 求结点的双亲时不方便。 R A B / C D / E / F G / H / K / 1 2 3 / 4 5 / 6 / 7 8 9 / T.nodes[ ]; T.n=10; T.r = 0;
例1:设树T以孩子链表为存储结构, 寻找值为x的双亲结点的算法如下 Status parent( Ctree T, TElem Type x /当值为x的结点不存在时返回2 ∥当值为x的结点为根结点时返回-1, ∥否则返回x结点的双亲结点的下标值 if(T nodes[T r] data ==x)return -1 值为x的结点为根结点; for(i=0;ichild]. data ! =X p->next fp) return(i),∥找到x的双亲结点 return-2;,∥/值为x的结点不存在
例1: 设树T以孩子链表为存储结构, 寻找值为x的双亲结点的算法如下: Status parent(Ctree T, TElemType x) {// 当值为x的结点不存在时返回-2; // 当值为x的结点为根结点时返回-1, // 否则返回x结点的双亲结点的下标值. if(T.nodes[T.r].data == x) return –1; //值为x的结点为根结点; for(i=0;ichild].data != x) p = p->next; if(p) return (i); // 找到x的双亲结点 } return –2; // 值为x的结点不存在 }
例2:删除值为x的结点的第i棵子树的 算法 delete如下 void delete( ctree &T int 删除树的第号结点及其子树 if! odes[i]. firstchild{∥删除叶结点 for(i=j;inext i=S->child free(s) deleted(T,i);∥/递归删除第i号结点及其子树
例2: 删除值为x的结点的第i棵子树的 算法delete如下： void deletej(Ctree &T, int j) {// 删除树T的第j号结点及其子树 if(!T.nodes[j].firstchild){ // 删除叶结点 for(i=j; inext; i = s->child; free(s); deletej(T, i); // 递归删除第i号结点及其子树 } } }
Status delete( ctree &T, TElemType x, int ∥/当值为x的结点不存在时返回2,当值为x的结点为 /叶结点或无第棵子树时返回-1,否则返回 for(k=0; k=Tn) return-2;∥值为x的结点不存在 Tnodes[k].firstchild if(lp) return-1:∥/x结点为叶结点 1){∥删除长子时,特殊处理 =p-> child;∥/记住要删除子树的下标 nodes[k]. firstchild=p->next; free(p); while(p->next & js1-Ikp=p->next:J++ next) return-1;∥无第i稞子树 ∥1指向第i-1个儿子 p>next> child;∥记住要删除子树的下标 s= p->next; p->next=S->next; free(s) delete((Tj);∥/递归删除第j号结点及其子树 return 1
Status delete(Ctree &T, TElemType x, int i) { // 当值为x的结点不存在时返回-2;当值为x的结点为 //叶结点或无第i 棵子树时返回-1, 否则返回1. for(k=0; k=T.n) return –2; // 值为x的结点不存在 p= T.nodes[k].firstchild; j = 1; if(!p) return –1; // x结点为叶结点 if(i==1){ // 删除长子时,特殊处理 j =p->child; // 记住要删除子树的下标 T.nodes[k].firstchild = p->next; free(p); }else{ while(p->next && jnext ; j++;} if(j>i-1 || !p->next) return –1; // 无第i 棵子树 // p指向第i-1 个儿子 j = p->next->child; // 记住要删除子树的下标 s = p->next; p->next = s->next; free(s); } deletej(T, j); // 递归删除第j号结点及其子树 return 1; }
孩子兄弟表示法 树的二叉树表示法(二叉链表示法) ∥-树的二叉链表(孩子兄弟)存储表示 typedef struct CSNode i ELem Type data struct CSNode * firstchild. * nextsibling I CSNode, * CSTree
三.孩子兄弟表示法 ---树的二叉树表示法(二叉链表示法) //-----树的二叉链表(孩子兄弟)存储表示------ typedef struct CSNode { ELemType data; struct CSNode *firstchild,*nextsibling; }CSNode, *CSTree;