Icoding题解

题干

树转二叉树

使用队列，编写transfrom函数，将普通树转换成对应的二叉树。二叉树的相关定义如下：

1
2
3
4
5
6
7
typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;

普通树节点的定义如下：

1
2
3
4
5
6
7
#define MAX_CHILDREN_NUM 5
struct _CSNode
{
    DataType data;
    struct _CSNode *children[MAX_CHILDREN_NUM];
};
typedef struct _CSNode CSNode;

其中，子树的根节点的指针存放在children数组的前k个元素中，即如果children[i]的值为NULL，而children[i-1]不为NULL，则表明该结点只有i棵子树，子树根结点分别保存在children[0]至children[i-1]中。

队列相关定义及操作如下：

1
2
3
4
5
6
7
8
9
10
11
12
struct __Queue
{
    int i, j; //指向数组内元素的游标
    void **array;
};
typedef struct __Queue Queue;

Queue* create_queue(); //创建队列
bool is_empty_queue(Queue *tree); //队为空返回true,不为空时返回false
void* del_queue(Queue *tree); //结点指针出队
void add_queue(Queue *tree, void *node); //结点指针入队
void free_queue(Queue *tree); //释放队列

transform函数定义如下：

1
BiTNode* transform(CSNode *root);

其中 root 为普通树的根结点，函数返回该树对应二叉树的根结点。

分析

  • 简要分析题干：
    将一个普通树转化成二叉树。实际上做起来并不是那么简单，需要队列的辅助。有些类似于层序遍历。
  • 应当注意的问题：
    1. 队列的基本操作
    2. 二叉树的操作，普通树的操作
  • 解题思路：
    1. 这里选择开两个队列，队列a用于存储普通树的结点，队列b用于存储二叉树的结点。
    2. 先把根复制到二叉树中，然后分别入队两个根
    3. 只要a队非空（原普通树的结点没有用完）就继续以下操作的循环
    4. a、b队列均出队一个结点
    5. 遍历a队的出队结点的孩子数组
    6. 第一个孩子作为b队列出队结点的左孩子，prev指针记录这个左孩子的位置。
    7. 普通树的第一个子节点作为二叉树中结点的左子节点，普通树中剩余的子节点按顺序作为二叉树中左子节点的右子节点链（当然可以选择其他的转换方法，笔者采用的方法会导致根节点没有右子树）

注释代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
BiTNode* transform(CSNode *root) {
    Queue* CSNodeQueue = create_queue();
    Queue* BiTNodeQueue = create_queue();

    //空间分配失败则返回
    if (!root || !CSNodeQueue || !BiTNodeQueue) {
        return NULL;
    }

    CSNode* CurrCSNode = NULL;
    CSNode* RootNode = NULL;
    BiTNode* CurrBiNode = (BiTree)malloc(sizeof(BiTNode));
    
    if (!CurrBiNode)
        return NULL;
    CurrBiNode->data = root->data;
    CurrBiNode->left = CurrBiNode->right = NULL;
    //此处是因为我们在最后需要返回二叉树根节点
    RootNode = CurrBiNode;
    //分别将根储存在队列中
    add_queue(CSNodeQueue, root);
    add_queue(BiTNodeQueue, CurrBiNode);

    //如果遍历完成了所有的普通树结点，就退出循环
    while (!is_empty_queue(CSNodeQueue)) {
        //首先出队之前入队的结点
        //我们需要这里的 CurrCSNode 的孩子
        //同理，我们将 CurrCSNode 的 Child 赋值给 CurrBiNode 的 Child
        CurrCSNode = del_queue(CSNodeQueue);
        CurrBiNode = del_queue(BiTNodeQueue);
        //TempNode用于暂存结点，后续会用到
        BiTNode* TempNode = NULL;
        for (int i = 0; i < MAX_CHILDREN_NUM; i++) {

            if (!CurrCSNode->children[i]) {
                break;
            } else {
                BiTree ChildBiNode = (BiTree)malloc(sizeof(BiTNode));
                ChildBiNode->data = CurrCSNode->children[i];
                ChildBiNode->left = ChildBiNode->right = NULL;

                //如果是普通树结点的第一个孩子结点，就将其作为二叉树左孩子
                //如果不是第一个孩子结点，将其作为二叉树孩子的右孩子
                if (i == 0) 
                    CurrBiNode->left = ChildBiNode;
                else
                    TempNode->right = ChildBiNode;
                //TempNode记录刚刚得到的孩子结点
                TempNode = ChildBiNode;
                //分别入队，继续下一次遍历
                add_queue(BiTNodeQueue, TempNode);
                add_queue(CSNodeQueue, CurrCSNode->children[i]);
            }

        }
    }

    free(BiTNodeQueue);
    free(CSNodeQueue);
    
    return CurrBiNode;
}

完整代码

有兴趣的可以自行探索，如何将普通二叉树转换为满二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
BiTNode* transform(CSNode *root){
    Queue* aqueue = create_queue();
    Queue* bqueue = create_queue();
    
    if(root == NULL)
        return NULL;
        
    BiTree BiRoot = (BiTree)malloc(sizeof(BiTNode));
    BiRoot->data = root->data;
    BiRoot->left = NULL;
    BiRoot->right = NULL;
    
    add_queue(bqueue, BiRoot);
    add_queue(aqueue, root);
    
    while(!is_empty_queue(aqueue))
    {
        BiTree curr_binode = del_queue(bqueue);
        CSNode *curr_node = del_queue(aqueue);
        BiTree prev = NULL;
        
        for(int i = 0; i < MAX_CHILDREN_NUM; i++)
        {
            if(curr_node->children[i] == NULL)
                break;
            else
            {
                BiTree child_binode = (BiTree)malloc(sizeof(BiTNode));
                child_binode->data = curr_node->children[i]->data;
                child_binode->left = NULL;
                child_binode->right = NULL;
                
                if(i == 0)
                    curr_binode->left = child_binode;
                else
                    prev->right = child_binode;
                
                prev = child_binode;
                
                add_queue(bqueue, prev);
                add_queue(aqueue, curr_node->children[i]);
            }
        }
    }
    
    free(aqueue);
    free(bqueue);
    
    return BiRoot;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。