二叉树还原成普通树

时间：2025-04-16 20:22:03

transform方法流程：
1、构造两个队列，普通树队列和二叉树队列。
2、将二叉树的根入队列，构造普通树的根顶点并入对应队列。
3、循环判断二叉树队列不为空。
4、从两个队列中分别取出一个元素，分别为bnode，node。
5、当bnode没有左孩子时，不考虑这种情况。因为此时的node没有孩子。
6、当bnode有左孩子时，构造普通树节点，数据为左孩子的数据。将该普通节点和左孩子分别入对应队列。同时让node的第一个孩子指针指向该树节点。(对同一个点而言二叉树的左孩子为树的第一个孩子)
7、从这个普通节点开始，一直寻找它的右孩子。每找到一个，对应构造一个二叉树节点。并将这些节点依次赋给node的孩子指针。同时将这些构造节点和二叉树的右孩子节点入队列。

#include <>
#include <>

#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 = 0;
    tree->j = 0;
    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 = 0;
    btree->j = 0;
    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=0; i<N; i++)
        root->childs[i] = NULL;

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

    while(emptyQueueBTree(bqueue) == 0)
    {
        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=0; i<N; i++)
                t0->childs[i] = NULL;
            node->childs[0] = t0;
            j = 1;
            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=0; 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[0] == NULL && root->childs[1] == NULL && root->childs[2] == NULL)
        free(root);
    else
    {
        if(root->childs[0] != NULL)
            destroyTree(root->childs[0]);
        if(root->childs[1] != NULL)
            destroyTree(root->childs[1]);
        if(root->childs[2] != NULL)
            destroyTree(root->childs[2]);
    }
}

void iterator(TreeNode *root) //树层序遍历
{
    if(root == NULL)
        return;
    QueueTree *queue = initQueueTree();
    addQueueTree(queue, root);
    while(emptyQueueTree(queue) == 0)
    {
        TreeNode *p = delQueueTree(queue);
        printf("%c ", p->data);
        int i;
        for(i=0; 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 0;
}

相关文章