首页 > 其他分享 >树、森林与二叉树的转换

树、森林与二叉树的转换

时间：2024-10-17 11:20:39浏览次数：9  
标签：结点 TreeNode int 二叉树 转换 NULL root 森林

一、引言与问题引出

        在计算机科学的数据结构领域中，树、森林与二叉树之间的转换具有重要意义。在实际研究过程中，我们常常会发现树的结构过于复杂，而二叉树相对简单。例如，普通的树形结构使用程序语言描述起来相对复杂，而二叉树则相对容易。一颗普通的树可以通过孩子兄弟表示法转换成二叉树，所以孩子兄弟表示法又被称为二叉树表示法。对于任意一颗树，都可以找到唯一的一颗二叉树与之对应。

        树是由 n (n>=0) 个结点组成的有限集，其中每个节点最多只有一个前驱节点可以有多个后继节点。森林则是由 n 棵树形成的有限集 (n>=0)。二叉树每个节点最多只能拥有两个子节点。这种结构上的差异使得在处理不同问题时，选择合适的数据结构变得至关重要。

        当我们面对复杂的树结构时，通过转换为二叉树，可以更方便地进行遍历、搜索等操作。同时，二叉树的一些特性，如深度为 k 的二叉树，最多可以有 2 的 k 次方 - 1 个节点等，也为我们分析和处理数据提供了便利。而森林与二叉树之间的转换，则可以让我们在处理多棵树组成的集合时，更加高效地利用二叉树的相关算法和性质。总之，树、森林与二叉树之间的转换为我们解决各种数据结构问题提供了有力的工具。

二、转换过程详述

（一）树转二叉树

        树转换为二叉树主要分为三个步骤。

        首先是加线，在所有兄弟结点之间加一条连线。例如对于树中的一组兄弟结点 A、B、C，连接 AB 和 BC。这样做的目的是为了明确兄弟节点之间的关系，为后续转换做准备。

        接着进行去线操作，对树中的每个结点，只保留它与第一个孩子结点的连线，删除它与其他孩子结点之间的连线。比如对于结点 X，若它有多个孩子结点 Y、Z、W，只保留 X 与 Y 的连线，删除 X 与 Z、W 的连线。这一步是为了将树的结构逐步向二叉树的结构靠近。

        最后进行层次调整，以树的根结点为轴心，将整个树顺时针旋转一定角度，使之层次分明。        

        经过这三个步骤，树就成功转换为二叉树。原理在于通过这些操作，利用树的孩子兄弟表示法，将一棵树用二叉链表进行存储，从而实现树与二叉树的转换。

（二）森林转二叉树

        森林转换为二叉树需要先将每个树转换为二叉树。假设森林中有三棵树，分别按照树转二叉树的步骤将每棵树转换为对应的二叉树。        然后，第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，用线链接起来。例如，第一棵二叉树的根结点为 A，第二棵二叉树的根结点为 B，将 B 连接到 A 的右孩子位置。这样依次连接，就完成了森林向二叉树的转换。这个过程的原理在于，森林是由若干棵树组成的，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

（三）二叉树转树

        二叉树转树确实是树转二叉树的逆过程。

        首先进行加线操作，若某结点的左孩子结点存在，则将这个左孩子的右孩子结点，右孩子的右孩子结点…… 都作为此节点的孩子，将该结点与这些右孩子结点用线连接起来。比如结点 X 的左孩子为 Y，Y 有右孩子 Z，将 X 与 Z 连接起来。

        接着进行去线操作，删除原二叉树中所有结点与其右孩子结点的连线。

        最后进行层次调整，使之结构层次分明。通过这三个步骤，二叉树就可以转换为树。

（四）二叉树转森林

        判断依据二叉树根结点有无右孩子确定转换为树或森林。如果二叉树的根结点没有右孩子，那么就可以转换为一棵树；如果有右孩子，则转换为森林。

        具体转换步骤如下：

        首先从根结点开始，若右孩子存在，则把与右孩子结点的连线删除。然后再看分离后的二叉树，若右孩子存在，则继续连线删除，直到所有右孩子连线都被删除为止，得到分离的二叉树。最后将分离的二叉树转换为树，这些树就组成了森林。

三、C 语言实现

（一）树转二叉树的 C 语言代码实现

以下是通过队列实现树层序遍历及构造二叉树的 C 语言代码：

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

// 定义通用数据类型
typedef int Datatype;

// 定义普通树节点结构体
typedef struct prototype_treeNode 
{
    Datatype data;
    // 假设最多有 N 个子节点
    struct prototype_treeNode* children[N];
} TreeNode, *Tree;

// 定义二叉树节点结构体
typedef struct prototype_biNode 
{
    Datatype data;
    struct prototype_biNode* lchild, *rchild;
} BiNode, *BiTree;

// 定义队列结构体
typedef struct prototype_queue 
{
    int front, rear;
    void** Que;
} Queue;

// 创建队列
Queue *createQueue() 
{
    Queue *new_que = (Queue*)malloc(sizeof(Queue));
    // 分配队列存储的指针数组内存
    new_que->Que = (void**)malloc(100 * sizeof(void*));
    new_que->front = 0;
    new_que->rear = 0;
    return new_que;
}

// 判断队列是否为空
bool isEmptyQueue(Queue *Q) 
{
    return Q->front == Q->rear? true : false;
}

// 出队操作
void* deQueue(Queue *Q) 
{
    if (isEmptyQueue(Q)) 
    {
        return NULL;
    }
    return Q->Que[Q->front++];
}

// 入队操作
void enQueue(Queue *Q, void* node) 
{
    Q->Que[Q->rear] = node;
    Q->rear++;
}

// 将普通树转换为二叉树
BiTree transform(TreeNode *root) 
{
    if (root == NULL) 
    {
        return NULL;
    }
    // 分配二叉树节点内存
    BiTree retNode = (BiTree)malloc(sizeof(BiNode));
    retNode->data = root->data;
    retNode->rchild = NULL;
    // 创建队列用于辅助转换
    Queue *que = createQueue();
    for (int i = 0; root->children[i]!= NULL; i++) 
    {
        enQueue(que, root->children[i]);
    }
    // 递归转换第一个子节点为左子树
    retNode->lchild = transform((TreeNode*)deQueue(que));
    BiNode *ptr = retNode->lchild;
    while (!isEmptyQueue(que)) 
    {
        // 递归转换后续子节点为右子树链
        ptr->rchild = transform((TreeNode*)deQueue(que));
        ptr = ptr->rchild;
    }
    // 释放队列内存
    free(que);
    return retNode;
}

（二）森林转二叉树的 C 语言代码实现

在多叉树构造、转化为二叉树及森林合成一棵二叉树的过程中，以下是 C 语言实现：

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct BiNode
{
    // 二叉树结点数据
    char data;
    BiNode *lChild;
    BiNode *rChild;
    BiNode():lChild(NULL),rChild(NULL){}
};

// 多叉树节点结构体
struct TreeNode
{
    // 多叉树结点数据
    char data;
    TreeNode **child;
    TreeNode(int B)
    {
        child = new TreeNode *[B];
        for(int i = 0; i < B;++i)
        {
            child[i]=NULL;
        }
    }
};

// 树类
class Tree
{
    TreeNode *root;
public:
    Tree()
    {
        root = CreateTree();
    }
    // 创建多叉树
    TreeNode* CreateTree();
    // 获取对应二叉树
    BiNode *getBiTree()
    {
        return transferToBT(root);
    }
    // 将多叉树转换为二叉树
    BiNode *transferToBT(TreeNode *t);
};

// 创建多叉树
TreeNode* Tree::CreateTree()
{
    TreeNode *p;
    char ch;
    cin >> ch;
    if(ch == '0')
    {
        p = NULL;
    }
     else 
    {
        p = new TreeNode(B);
        p->data = ch;
        for(int j = 0; j < B; j++)
        {
            p->child[j]=CreateTree();
        }
    }
    return p;
}

// 将多叉树转换为二叉树
BiNode* Tree::transferToBT(TreeNode *t)
{
    BiNode *p = NULL;
    if(t)
    {
        p = new BiNode;
        p->data = t->data;
        p->lChild = transferToBT(t->child[0]);
        if(p->lChild)
        {
            BiNode *q = p->lChild;
            for(int i = 1; i < B;++i)
            {
                q->rChild = transferToBT(t->child[i]);
                if(q->rChild)
                {
                    q = q->rChild;
                }
            }
        }
    }
    return p;
}

// 二叉树操作类
class BiTree
{
    BiNode *root;
    // 输出叶子结点编码
    void get_leaves(BiNode *t, string str)
    {
        if(t)
        {
            if(!t->lChild &&!t->rChild)
            {
                cout << str << endl;
            }
            get_leaves(t->lChild, str + "0 ");
            get_leaves(t->rChild, str + "1 ");
        }
    }
public:
    // 合并森林
    void merge(BiNode **t,int N)
    {
        root = t[0];
        for(int i = 0; i < N - 1;++i)
        {
            t[i]->rChild = t[i + 1];
        }
    }
    // 获取叶子编码
    void get_leavesCode()
    {
        string str = "";
        get_leaves(root, str);
    }
};

int main()
{
    int N;
    // 输入森林中树的数量和多叉树的分支数量
    cin >> N >> B;
    // 创建 N 棵树对象
    Tree *p = new Tree[N];
    // 创建 N 个指向二叉树节点的指针数组
    BiNode **q = new BiNode *[N];
    for(int i = 0; i < N;++i)
    {
        // 获取每棵树的二叉树
        q[i]= p[i].getBiTree();
    }
    BiTree biT;
    // 合并森林中的二叉树
    biT.merge(q, N);
    // 获取叶子编码
    biT.get_leavesCode();
    return 0;
}

（三）二叉树转树的 C 语言代码实现

二叉树转树是树转二叉树的逆过程。以下是 C 语言实现过程：

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

// 二叉树节点结构
typedef struct BiTreeNode {
    int data;
    struct BiTreeNode *left;
    struct BiTreeNode *right;
} BiTreeNode;

// 树节点结构
typedef struct TreeNode {
    int data;
    struct TreeNode **children;
    int numChildren;
} TreeNode;

// 创建二叉树节点
BiTreeNode* createBiTreeNode(int data) {
    BiTreeNode *node = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 创建树节点
TreeNode* createTreeNode(int data) {
    TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->children = NULL;
    node->numChildren = 0;
    return node;
}

// 二叉树转树
TreeNode* biTreeToTree(BiTreeNode *root) {
    if (root == NULL) {
        return NULL;
    }
    TreeNode *treeNode = createTreeNode(root->data);
    TreeNode *leftTree = biTreeToTree(root->left);
    TreeNode *rightTree = biTreeToTree(root->right);
    if (leftTree!= NULL) {
        treeNode->numChildren++;
        treeNode->children = (TreeNode**)realloc(treeNode->children, treeNode->numChildren * sizeof(TreeNode*));
        treeNode->children[treeNode->numChildren - 1] = leftTree;
    }
    if (rightTree!= NULL) {
        treeNode->numChildren++;
        treeNode->children = (TreeNode**)realloc(treeNode->children, treeNode->numChildren * sizeof(TreeNode*));
        treeNode->children[treeNode->numChildren - 1] = rightTree;
    }
    return treeNode;
}

// 释放二叉树内存
void freeBiTree(BiTreeNode *root) {
    if (root == NULL) {
        return;
    }
    freeBiTree(root->left);
    freeBiTree(root->right);
    free(root);
}

// 释放树内存
void freeTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    for (int i = 0; i < root->numChildren; i++) {
        freeTree(root->children[i]);
    }
    free(root->children);
    free(root);
}

// 中序遍历二叉树（用于测试）
void inorderTraversalBiTree(BiTreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversalBiTree(root->left);
    printf("%d ", root->data);
    inorderTraversalBiTree(root->right);
}

// 先序遍历树（用于测试）
void preorderTraversalTree(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->data);
    for (int i = 0; i < root->numChildren; i++) {
        preorderTraversalTree(root->children[i]);
    }
}

int main() {
    // 创建二叉树
    BiTreeNode *biTreeRoot = createBiTreeNode(1);
    biTreeRoot->left = createBiTreeNode(2);
    biTreeRoot->right = createBiTreeNode(3);
    biTreeRoot->left->left = createBiTreeNode(4);
    biTreeRoot->left->right = createBiTreeNode(5);

    // 中序遍历二叉树测试
    printf("二叉树中序遍历结果：");
    inorderTraversalBiTree(biTreeRoot);
    printf("\n");

    // 二叉树转树
    TreeNode *treeRoot = biTreeToTree(biTreeRoot);

    // 先序遍历树测试
    printf("转换后的树先序遍历结果：");
    preorderTraversalTree(treeRoot);
    printf("\n");

    // 释放内存
    freeBiTree(biTreeRoot);
    freeTree(treeRoot);

    return 0;
}

（四）二叉树转森林的 C 语言代码实现

判断一棵二叉树能否转换为森林，主要看二叉树的根结点是否有右孩子。以下是实现步骤：

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

// 树节点结构
typedef struct TreeNode {
    int data;
    int numChildren;
    struct TreeNode** children;
} TreeNode;

// 创建树节点
TreeNode* createTreeNode(int data) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = data;
    newNode->numChildren = 0;
    newNode->children = NULL;
    return newNode;
}

// 将二叉树转换为森林
TreeNode** biTreeToForest(TreeNode* root, int* numTrees) {
    if (root == NULL) {
        // 如果二叉树为空，设置森林中的树数量为 0 并返回空指针
        *numTrees = 0;
        return NULL;
    }
    TreeNode** forest = (TreeNode**)malloc(sizeof(TreeNode*));
    *numTrees = 0;
    if (root->left == NULL && root->right == NULL) {
        // 如果二叉树只有一个节点，创建一个树节点并加入森林
        forest[(*numTrees)++] = createTreeNode(root->data);
        return forest;
    }
    TreeNode** leftForest = biTreeToForest(root->left, numTrees);
    TreeNode** rightForest = biTreeToForest(root->right, numTrees);
    int totalTrees = *numTrees;
    // 重新分配内存以容纳新的树节点
    forest = (TreeNode**)realloc(forest, (totalTrees + 1) * sizeof(TreeNode*));
    forest[totalTrees++] = createTreeNode(root->data);
    for (int i = 0; i < totalTrees - 1; i++) {
        forest[i]->numChildren++;
        // 重新分配内存以容纳新的子节点
        forest[i]->children = (TreeNode**)realloc(forest[i]->children, forest[i]->numChildren * sizeof(TreeNode*));
        forest[i]->children[forest[i]->numChildren - 1] = forest[totalTrees - 1];
    }
    if (leftForest!= NULL) {
        for (int i = 0; i < *numTrees; i++) {
            forest[i]->numChildren++;
            forest[i]->children = (TreeNode**)realloc(forest[i]->children, forest[i]->numChildren * sizeof(TreeNode*));
            forest[i]->children[forest[i]->numChildren - 1] = leftForest[i];
        }
        free(leftForest);
    }
    if (rightForest!= NULL) {
        for (int i = 0; i < *numTrees; i++) {
            forest[i]->numChildren++;
            forest[i]->children = (TreeNode**)realloc(forest[i]->children, forest[i]->numChildren * sizeof(TreeNode*));
            forest[i]->children[forest[i]->numChildren - 1] = rightForest[i];
        }
        free(rightForest);
    }
    *numTrees = totalTrees;
    return forest;
}

四、总结与展望

        树、森林与二叉树之间的转换在数据结构领域中具有重要的地位。通过对它们之间转换过程的深入理解和 C 语言实现，我们可以更好地处理各种复杂的数据结构问题。

        在转换过程中，我们看到了树和森林通过特定的步骤可以转换为二叉树，而二叉树也可以逆向转换回树或森林。这些转换不仅在理论上具有重要意义，而且在实际的编程应用中也非常实用。例如，在处理大规模的树或森林结构数据时，将其转换为二叉树可以简化算法的设计和实现，提高程序的效率。

        C 语言实现的代码为我们提供了具体的工具来进行这些转换。通过不同的函数和算法，我们可以实现树转二叉树、森林转二叉树、二叉树转树以及二叉树转森林的操作。这些代码不仅展示了数据结构转换的具体实现方法，也为我们进一步探索数据结构的应用提供了参考。

        然而，这仅仅是一个开始。在未来，我们可以进一步探索更高效的转换算法和实现方法。例如，可以研究如何优化转换过程中的时间复杂度和空间复杂度，以提高程序的性能。同时，我们也可以将这些转换应用到更广泛的领域，如图形学、数据库管理等，为解决实际问题提供更多的解决方案。

        最后，鼓励读者通过做一些练习题来巩固所学的知识。只有通过不断地实践和探索，我们才能更好地掌握树、森林与二叉树之间的转换以及数据结构的其他重要概念。让我们一起努力，深入学习数据结构，为计算机科学的发展做出贡献。

标签：结点,TreeNode,int,二叉树,转换,NULL,root,森林
From： https://blog.csdn.net/m0_71974552/article/details/142953403

相关文章

  • LeetCode第六题：锯齿形转换（Python）
    一.题目要求及实例将给定的字符串，转化为锯齿形。锯齿形的行数给定。按序输出转换后的字符串。二.初始思路（1）二维数组的大小竖着写入二维数组较困难，所以想到了先横着写，再取转置。首先需要知道二维数组的大小。参数中给的numRows即为行数，所以要考虑的就是二维数组的列数。......
  • 实现对象字段在转换为 JSON 时大小写保持不变
    实现对象字段在转换为JSON时大小写保持不变预期效果：对象中字段名是Age，NAME转成json后：{"Age":"12","NAME":"张三"}使用场景：给外系统传参数rest接口参数时，对方要求；方式一使用Jackson的@JsonProperty注解importcom.fasterxml.jackson.annotation.JsonProperty;import......
  • 代码随想录|二叉树part 03
    求普通二叉树的节点数量要点：将子节点的个数记录到父节点，使用后序遍历classSolution{public:intmaxDepth(TreeNode*root){if(root==NULL)return0;intleft1=maxDepth(root->left);intright1=maxDepth(root->right);intnum=......
  • 代码随想录|二叉树part 02
    翻转二叉树要点：指针交换优先利用前序或后序遍历，若采用中序遍历（则两次采用遍历左子树）classSolution{public:TreeNode*invertTree(TreeNode*root){if(root==NULL)returnroot;swap(root->left,root->right);invertTree(root->left);......
  • PostgreSQL中将对象oid和对象名相互转换
    文章目录PostgreSQL中将对象oid转为对象名数据库类型转换对应类型的oid对应关系创建测试数据将对象名转为oid类型转换关系测试示例PostgreSQL中将对象oid转为对象名使用pg的内部数据类型将对象oid转为对象名，可以简化一些系统视图的关联查询。数据库类型转换对应类......
  • mysql的时间在vue中显示相差8个小时 (Vue+Django+MySQL 时区 自动转换时间)
    mysql的时间在vue中显示相差8个小时 Vue     10:00:00Django (USE_TZ=True,Django会自动根据所设的时区对时间进行转换;改为False即可)MySQL  2:00:00 =========================原因:中间某个环节的时区不对. 我这里是mysql的时区不对.解决办法:......
  • 代码随想录算法训练营day17| 654.最大二叉树 617.合并二叉树 700.二叉搜索树中的搜
    学习资料：https://programmercarl.com/0654.最大二叉树.html#算法公开课用前序遍历构造二叉树二叉搜索树的特点，其左节点的值<每个节点的值<其右节点的值，且根节点的值大于它的左子树的所有节点的值，小于它右子树的所有节点的值，其他同理。二叉搜索树的搜索和验证时不关心遍历顺序，因......
  • 2024年顶级免费货币转换API推荐
    如果您与国际客户合作，那么您需要掌握最新的货币信息。然而，汇率每天都在迅速变化，因此很难获得准确的价值。通过使用 货币转换器API，您可以毫不费力地获得实时货币汇率。此外，它也非常容易集成到您的网络应用程序中。您只需编写几行代码即可。通过这种方式，API可以帮助您节省时......
  • 算法-二叉树展开单链表
    这道题我们可以利用栈来做，利用栈先进后出的特性每次先加入右节点再加入左节点，这样的话弹出的时候正好左节点在前面，右节点在后面满足题目要求。然后至于是构造单链表，我们可以用一个prev节点prev的left永远都是null而prev的right永远都等于cur 因为每次curr都是栈内弹出来......
  • C语言手撕实战代码_线索二叉树_先序中序线索二叉树_树的先根遍历_后根遍历_树的度_孩
    文章目录1.设计算法构造一棵先序线索二叉树2.先序线索二叉树的先序遍历算法3.设计算法构造一棵中序线索二叉树4.遍历中序线索二叉树5.树的先根遍历和后根遍历6.树T的叶子结点个数7.计算一棵以孩子兄弟表示的树T的度，该算法的时间复杂度为O(n)8.计算树孩子兄弟链表表示的T......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99