孩子链表存储表示举例 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;i<Tn;i计+ i p-Tnodes i]. firstchild while(p & T nodes[p->child]. 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;i<T.n;i++) { p=T.nodes[i].firstchild; while(p && T.nodes[p->child].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;i<in-1;计++){号结点后的结点全部前移一位 nodes il. data T nodes i+ldata T nodes[i]. firstchild= T nodes[i+]. firstchild .n-- Else while(s-T nodes[i]. firstchild)i T. nodesli] firstchild=S->next 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; i<T.n-1; i++) { // j号结点后的结点全部前移一位 T.nodes[i].data = T.nodes[i+1].data; T.nodes[i].firstchild = T.nodes[i+1].firstchild; } T.n--; }else{ while(s=T.nodes[j].firstchild){ T.nodes[j].firstchild = s->next; i = s->child; free(s); deletej(T, i); // 递归删除第i号结点及其子树 } } }
Status delete( ctree &T, TElemType x, int ∥/当值为x的结点不存在时返回2,当值为x的结点为 /叶结点或无第棵子树时返回-1,否则返回 for(k=0; k<T n; k++ if(T nodes[k]. data=x) break;,∥找到值为x的结点 f〔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; k++) if(T.nodes[k].data == x) break; // 找到值为x的结点 if(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 && j<i-1){p = p->next ; 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;