数据结构
6 分钟 读完 (大约 825 个字)

二叉树与森林的转换

思路

  • 利用递归建立节点完成转换。首先我们观察二叉树的结构，包含第一个孩子，及其兄弟。关键在于：那么我们在构造递归时，每层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
//Another Method:
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
}

有两种方法的思路不同：前者是按单个节点完成递归，而后者则是按照层来递归(虽然二者都是深度优先)，后者更像是图的遍历方法。

# ,
AC自动机及多模式匹配
建堆O(n)时间复杂度证明
关注我

链接

分类

标签云

A-star AC自动机 Android Android Studio C++ CRC Cluster Git Github Github Page Image Search Java JekyII LeetCode LintCode OpenCV Prisoner's Dilemma Pseudo-random Python RxJava Tsinghua University heap 二叉树 堆 大数乘法 左偏树 斜堆 时间复杂度 森林 自动化部署

归档

标签

A-star 1
AC自动机 1
Android 3
Android Studio 1
C++ 1
CRC 1
Cluster 1
Git 2
Github 2
Github Page 2
Image Search 1
Java 1
JekyII 1
LeetCode 23
LintCode 11
OpenCV 1
Prisoner's Dilemma 1
Pseudo-random 1
Python 2
RxJava 1
Tsinghua University 1
heap 1
二叉树 1
堆 1
大数乘法 1
左偏树 1
斜堆 1
时间复杂度 1
森林 1
自动化部署 1
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×