C语言数据结构-树和二叉树-树转二叉树-使用队列，编写transfrom函数，将普通树转换成对应的二叉树

清疚 2023-01-13 04:19 95阅读 0赞

# 树转二叉树 #

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

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

普通树节点的定义如下：

#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\]中。

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

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函数定义如下：

BiTNode* transform(CSNode *root);

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

### **提供代码** ###

#include <stdlib.h>
    #include <stdio.h>
    #include "bitree.h" //请不要删除，否则检查不通过
    
    
    BiTNode* transform(CSNode *root){
    
    
    }

### 解析思路 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70][]

### **参考代码** ###

BiTNode* transform(CSNode* root)
    {
        if (root == NULL)
            return NULL;
            
        //初始化二叉树的根节点
        BiTree broot = (BiTree)malloc(sizeof(struct Node));
        broot->data = root->data;
        broot->left = broot->right = NULL;
        
        //普通树、二叉树初始化、加入队列
        Queue* queue = create_queue();
        Queue* bqueue = create_queue();
        add_queue(queue, root);
        add_queue(bqueue, broot);
        
        while (!is_empty_queue(queue))
    	{
            //从普通数和二叉树中分别取出一个结点
            CSNode* node = del_queue(queue);
            BiTree bTreeNode = del_queue(bqueue);
            
            int i;
            BiTree former = NULL;
            //遍历普通树结点的所有孩子结点，将孩子加入队列
            for (i = 0; i < MAX_CHILDREN_NUM; i++) 
    		{
    			//孩子非空
                if (node->children[i]) 
    			{
    				//二叉树节点初始化并赋值
                    BiTree bnode = (BiTree)malloc(sizeof(struct Node));
                    bnode->left = bnode->right = NULL;
                    bnode->data = node->children[i]->data;
    				
                    if (i == 0)//普通树的第一个孩子作为二叉树的左孩子
                        bTreeNode->left = bnode;
                     else //后面的孩子结点作为前面结点的右孩子
                        former->right = bnode;
                    former = bnode;
                    
                    add_queue(queue, node->children[i]);
                    add_queue(bqueue, bnode);
                }
            }
        }
        free(queue->array);
        free(queue);
        free(bqueue->array);
        free(bqueue);
        return broot;
    }

### 解析：数组树 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1][]

### 解析：二叉链表的树和二叉树没区别 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70]: /images/20221022/8081bdfdcc614cf0afa07b67ed15318d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 1]: /images/20221022/ab4f96d5310b4d10b16e033f8910a9f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FpcXExMzY_size_16_color_FFFFFF_t_70 2]: /images/20221022/ceba2818e64d4c2c992cdca058f39aa8.png