思路
- 利用递归建立节点完成转换。首先我们观察二叉树的结构,包含第一个孩子,及其兄弟。关键在于:那么我们在构造递归时,每层recursion中都必须找到对应sibling和firstchild。对于双亲表示法,我们很难找到孩子,对于孩子表示法,我们很难找到双亲(因为找到双亲是找到本节点兄弟的唯一方法,或在传参时也传入父节点指针)。
- 不同形式间转换的技巧。对于要被转换的结构,需要传入针对它单次recursion完成结构内部所有成员构造对应的转换的结构的信息。就能完成一层递归。同时应注意递归结束的条件。
孩子表示法生成二叉树算法
1 | typedef struct BiTree{ |
2 | ElemType data; |
3 | struct BiTree *firstchild, *sibling; |
4 | }BTnode, *BTree; |
5 |
|
6 | typedef struct Lnode{ |
7 | int child; |
8 | struct Lnode *next; |
9 | }Lnode, *CList; |
10 | typedef struct Cbox{ |
11 | ElemType data; |
12 | CList firstchild; |
13 | }Cbox, *Cnode; |
14 | typedef struct CTnode{ |
15 | Cnode node; |
16 | int n, r; |
17 | }CTree; |
18 |
|
19 | void TransformChildTreeToBinaryTree(CTree CT, BTree &BT, int preroot, int root){ |
20 | if (root == -1){ |
21 | BT = NULL; return; |
22 | } |
23 | BT = (BTree)malloc(sizeof(BTnode)); |
24 | BT->data = CT.node[root].data; |
25 | int rsave; |
26 | if (CT.node[root].firstchild){ |
27 | rsave = CT.node[root].firstchild->child; |
28 | } |
29 | else{ |
30 | rsave = -1; |
31 | } |
32 | TransformChildTreeToBinaryTree(CT, BT->firstchild, root, rsave); |
33 | if (preroot == -1){ |
34 | BT->sibling = NULL; return; |
35 | } |
36 | CList p = CT.node[preroot].firstchild; |
37 | while (p && p->data != root){ |
38 | p = p->next; |
39 | } |
40 | if (p->next){ |
41 | rsave = p->next->child; |
42 | } |
43 | else{ |
44 | rsave = -1; |
45 | } |
46 | TransformChildTreeToBinaryTree(CT, BT->sibling, preroot, rsave); |
47 | return; |
48 | } |
孩子双亲表示法生成二叉树(类似于孩子表示法)
1 | typedef struct BTnode{ |
2 | ElemType data; |
3 | struct BTnode *firstchild, *sibling; |
4 | }BTnode, *BTree; |
5 |
|
6 | typedef struct Cnode{ |
7 | int child; |
8 | struct Cnode *next; |
9 | }Cnode, *CList; |
10 | typedef struct CTnode{ |
11 | int parent; |
12 | ElemType data; |
13 | CList firstchild; |
14 | }CTnode, *CTbox; |
15 | typedef struct PCTnode{ |
16 | CTbox node; |
17 | int r, n; |
18 | }PCTree; |
19 |
|
20 | void TransformPCTreeToBiTree(PCTree PC, BTree &BT, int root){ |
21 | if (root == -1){ |
22 | BT = NULL; return; |
23 | } |
24 | BT = (BTree)malloc(sizeof(BTnode)); |
25 | BT->data = PC.node[root].data; |
26 | int rsave, tmp; |
27 | if (PC.node[root].firstchild){ |
28 | rsave = PC.node[root].firstchide->child; |
29 | } |
30 | else{ |
31 | rsave = -1; |
32 | } |
33 | TransformPCTreeToBiTree(PC, BT->firstchild, rsave); |
34 | tmp = PC.node[root].parent; |
35 | if (tmp == -1){ |
36 | BT->sibling = NULL; return; |
37 | } |
38 | else{ |
39 | LList p = PC.node[tmp].firstchild; |
40 | while (p && p->child != root){ |
41 | p = p->next; |
42 | } |
43 | if (p->next){ |
44 | rsave = p->next->child; |
45 | } |
46 | else{ |
47 | rsave = -1; |
48 | } |
49 | TransformPCTreeToBiTree(PC, BT->sibling, rsave); |
50 | return; |
51 | } |
52 | } |
同构链式孩子表示法生成二叉树
1 | typedef struct BTnode{ |
2 | ElemType data; |
3 | struct BTnode *firstchild, *sibling; |
4 | }BTnode, *BTree; |
5 |
|
6 | #define DEGREE 5 |
7 | typedef struct LCTnode{ |
8 | ElemType data; |
9 | struct LCTnode *child[DEGREE]; |
10 | }LCTnode, *LCTree; |
11 |
|
12 |
|
13 | BTree InitialTransLCTree2BiTree(LCTree root){ |
14 | if (!root){ |
15 | return NULL; |
16 | } |
17 | BTree BTroot = (BTree)malloc(sizeof(BTnode)); |
18 | BTroot->data = LCTree->data; |
19 | BTroot->sibling = NULL; |
20 | TransformLinkedChildTreeToBinaryTree(BTroot->firstchild, root, 0); |
21 | return BTroot; |
22 | } |
23 | void TransformLinkedChildTreeToBinaryTree(BTree &BT, LCTree LCT, int i){ |
24 | if (i >= DEGREE || !LCT->child[i]){ |
25 | BT = NULL; return; |
26 | } |
27 | BT = (BTree)malloc(sizeof(BTnode)); |
28 | BT->data = LCT->child[i]->data; |
29 | TransformLinkedChildTreeToBinaryTree(BT, LCT->sibling, i + 1); |
30 | TransformLinkedChildTreeToBinaryTree(BT->child[i], LCT->firstchild, 0); |
31 | return; |
32 | } |
异构链式孩子表示法生成二叉树
1 | typedef struct BTnode{ |
2 | ElemType data; |
3 | struct BTnode *firstchild, *sibling; |
4 | }BTnode, *BTree; |
5 |
|
6 | #ifdef DEGREE |
7 | #undef DEGREE |
8 | #define DEGREE 5 |
9 | #endif |
10 |
|
11 | typedef struct LCTnode{ |
12 | ElemType data; |
13 | struct LCTnode * *child; |
14 | int degree; |
15 | }LCTnode, *LCTree; |
16 |
|
17 | void TransformLCTree2BinaryTree(LCTree LCT, BTree &BT, int i){ |
18 | if (i >= LCT->degree || !LCT->child[i]){ |
19 | BT = NULL; return; |
20 | } |
21 | BT = (BTree)malloc(sizeof(BTnode)); |
22 | BT->data = LCT->child[i]->data; |
23 | TransformLCTree2BinaryTree(LCT, BT->sibling, i + 1); |
24 | TransformLCTree2BinaryTree(LCT->child[i], BT->firstchild, 0); |
25 | return; |
26 | } |
27 |
|
28 |
|
29 | void TransformLCTree2BinaryTree2(LCTree LCT, BTree &BT){ |
30 | if (!LCT->child[0]){ |
31 | BT = NULL; return; |
32 | } |
33 | BTree p, q; |
34 | for (int i = 0; i < LCT->degree && LCT->child[i]; ++i){ |
35 | BTree q = (BTree)malloc(sizeof(BTnode)); |
36 | q->data = LCT->child[i]->data; |
37 | q->sibling = NULL; |
38 | q->firstchild = NULL; |
39 | if (!BT){ |
40 | BT = q; |
41 | p = q; |
42 | } |
43 | else{ |
44 | q->sibling = p->sibling; p->sibling = q; |
45 | p = q; |
46 | } |
47 | TransformLCTree2BinaryTree2(LCT->child[i], q->firstchild); |
48 | return; |
49 | } |
50 | } |
有两种方法的思路不同:前者是按单个节点完成递归,而后者则是按照层来递归(虽然二者都是深度优先),后者更像是图的遍历方法。