二叉樹還原成普通樹

transform方法流程：

1、構造兩個隊列，普通樹隊列和二叉樹隊列。

2、将二叉樹的根入隊列，構造普通樹的根頂點并入對應隊列。

3、循環判斷二叉樹隊列不為空。

4、從兩個隊列中分别取出一個元素，分别為bnode，node。

5、當bnode沒有左孩子時，不考慮這種情況。因為此時的node沒有孩子。

6、當bnode有左孩子時，構造普通樹節點，資料為左孩子的資料。将該普通節點和左孩子分别入對應隊列。同時讓node的第一個孩子指針指向該樹節點。(對同一個點而言二叉樹的左孩子為樹的第一個孩子)

7、從這個普通節點開始，一直尋找它的右孩子。每找到一個，對應構造一個二叉樹節點。并将這些節點依次賦給node的孩子指針。同時将這些構造節點和二叉樹的右孩子節點入隊列。

#include <stdio.h>
#include <stdlib.h>

#define N 3 //定義每個節點的最大孩子數
#define M 9 //定義樹中節點的個數

struct TreeNode
{
    char data;
    struct TreeNode *childs[N];
};
typedef struct TreeNode TreeNode; //定義類型

struct BTreeNode
{
    char data;
    struct BTreeNode *lchild, *rchild;
};
typedef struct BTreeNode BTreeNode;

/*------------------普通樹的隊列開始--------------------*/
struct QueueTree
{
    int i, j;
    TreeNode **queue;
};
typedef struct QueueTree QueueTree;

QueueTree * initQueueTree()
{
    //配置設定一個隊列空間
    QueueTree *tree = (QueueTree *)malloc(sizeof(QueueTree)); 
    //配置設定M個樹節點指針空間
    tree->queue = (TreeNode **)malloc(sizeof(TreeNode *)*M); 
    tree->i = ;
    tree->j = ;
    return  tree;
};

void freeQueueTree(QueueTree *tree) //釋放配置設定空間
{
    free(tree->queue);
    free(tree);
}

void addQueueTree(QueueTree *tree, TreeNode *node) //加入隊列
{
    if(tree->j == M) //隊列已滿
        return;
    tree->queue[tree->j] = node;
    tree->j++;
}

TreeNode * delQueueTree(QueueTree *tree)
{
    if(tree->i == tree->j) //隊列已空
        return NULL;
    TreeNode *node = tree->queue[tree->i];
    tree->i++;
    return node;
}

int emptyQueueTree(QueueTree *tree)
{
    return tree->i==tree->j; //1空
}
/*--------------------普通樹的隊列結束----------------------*/

/*--------------------二叉樹的隊列開始----------------------*/
struct QueueBTree
{
    int i, j;
    BTreeNode **queue;
};
typedef struct QueueBTree QueueBTree;

QueueBTree * initQueueBTree()
{
    //配置設定一個隊列空間
    QueueBTree *btree = (QueueBTree *)malloc(sizeof(QueueBTree)); 
    //配置設定M個樹節點指針空間
    btree->queue = (BTreeNode **)malloc(sizeof(BTreeNode *)*M); 
    btree->i = ;
    btree->j = ;
    return  btree;
}

void freeQueueBTree(QueueBTree *btree) //釋放配置設定空間
{
    free(btree->queue);
    free(btree);
}

void addQueueBTree(QueueBTree *btree, BTreeNode *node) //加入隊列
{
    if(btree->j == M) //隊列已滿
        return;
    btree->queue[btree->j] = node;
    btree->j++;
}

BTreeNode * delQueueBTree(QueueBTree *tree)
{
    if(tree->i == tree->j) //隊列已空
        return NULL;
    BTreeNode *node = tree->queue[tree->i];
    tree->i++;
    return node;
}

int emptyQueueBTree(QueueBTree *tree)
{
    return tree->i==tree->j; //1空
}
/*--------------------二叉樹的隊列結束----------------------*/
           

上面定義的是需要用到的隊列以及一些方法。轉化方法如下：

TreeNode * transform(BTreeNode *broot)
{
    int i, j;
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->data = broot->data;
    for(i=; i<N; i++)
        root->childs[i] = NULL;

    QueueTree *queue = initQueueTree();
    addQueueTree(queue, root);
    QueueBTree *bqueue = initQueueBTree();
    addQueueBTree(bqueue, broot);

    while(emptyQueueBTree(bqueue) == )
    {
        BTreeNode *bnode = delQueueBTree(bqueue);
        TreeNode *node = delQueueTree(queue);

        if(bnode->lchild != NULL)
        {
            TreeNode *t0 = (TreeNode *)malloc(sizeof(TreeNode));

            t0->data = bnode->lchild->data;
            for(i=; i<N; i++)
                t0->childs[i] = NULL;
            node->childs[] = t0;
            j = ;
            BTreeNode *p = bnode->lchild;
            addQueueBTree(bqueue, p);
            addQueueTree(queue, t0);
            while(p->rchild != NULL)
            {
                p = p->rchild;
                TreeNode *tj = (TreeNode *)malloc(sizeof(TreeNode));
                tj->data = p->data;
                for(i=; i<N; i++)
                    tj->childs[i] = NULL;
                node->childs[j++] = tj;
                addQueueBTree(bqueue, p);
                addQueueTree(queue, tj);
            }
        }
    }
    return root;
}
           

代碼運作還需要完成以下功能。構造二叉樹，二叉樹周遊，普通樹周遊，main方法，樹空間釋放。

/*二叉樹的構造開始*/
BTreeNode * initTree()
{
    BTreeNode *root = (BTreeNode *)malloc(sizeof(BTreeNode));
    root->data = 'a';
    BTreeNode *p1 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p1->data = 'b';
    BTreeNode *p2 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p2->data = 'c';
    BTreeNode *p3 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p3->data = 'd';
    BTreeNode *p4 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p4->data = 'e';
    BTreeNode *p5 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p5->data = 'f';
    BTreeNode *p6 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p6->data = 'g';
    BTreeNode *p7 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p7->data = 'h';
    BTreeNode *p8 = (BTreeNode *)malloc(sizeof(BTreeNode));
    p8->data = 'i';

    root->lchild = p1;
    root->rchild = NULL;
    p1->lchild = p4;
    p1->rchild = p2;
    p2->lchild = NULL;
    p2->rchild = p3;
    p3->lchild = p7;
    p3->rchild = NULL;
    p4->lchild = NULL;
    p4->rchild = p5;
    p5->lchild = NULL;
    p5->rchild = p6;
    p6->lchild = NULL;
    p6->rchild = NULL;
    p7->lchild = NULL;
    p7->rchild = p8;
    p8->lchild = NULL;
    p8->rchild = NULL;
    return root;
}

void destroyTree(TreeNode *root) //樹空間釋放
{
    if(root == NULL)
        return;
    if(root->childs[] == NULL && root->childs[] == NULL && root->childs[] == NULL)
        free(root);
    else
    {
        if(root->childs[] != NULL)
            destroyTree(root->childs[]);
        if(root->childs[] != NULL)
            destroyTree(root->childs[]);
        if(root->childs[] != NULL)
            destroyTree(root->childs[]);
    }
}

void iterator(TreeNode *root) //樹層序周遊
{
    if(root == NULL)
        return;
    QueueTree *queue = initQueueTree();
    addQueueTree(queue, root);
    while(emptyQueueTree(queue) == )
    {
        TreeNode *p = delQueueTree(queue);
        printf("%c ", p->data);
        int i;
        for(i=; i<N; i++)
        {
            if(p->childs[i] != NULL)
            {
                addQueueTree(queue, p->childs[i]);
            }
        }
    }
    freeQueueTree(queue);
}
void preOrder(BTreeNode *root) //二叉樹前序周遊
{
    if(root == NULL)
        return;
    printf("%c ", root->data);
    preOrder(root->lchild);
    preOrder(root->rchild);
}

void destroyBTree(BTreeNode *root) //二叉樹空間釋放
{
    if(root == NULL)
        return;
    if(root->lchild == NULL && root->rchild == NULL)
        free(root);
    else
    {
        if(root->lchild != NULL)
            destroyBTree(root->lchild);
        if(root->rchild != NULL)
            destroyBTree(root->rchild);
    }
}

int main()
{
    BTreeNode *root = initTree();
    preOrder(root); //前序輸出二叉樹
    printf("\n");
    TreeNode *broot = transform(root);
    iterator(broot); //層序輸出普通樹
    destroyBTree(root);
    destroyTree(broot);
    return ;
}