二叉树转化为森林例子要怎么实现?步骤有哪些?

TheDisguiser 2020-06-02 22:18:09 java常见问答 7780

二叉树相信小伙伴们已经不陌生了,这是计算机中一个重要的数据结构,那么你们知道二叉树要如何转化为森林吗?快看下面吧。

首先,二叉树转换为森林的前提则是它的根节点中必须有右孩子,不然它就会转换成一棵树。

1)、假如,想要转换成森林,从根节点开始,如果右孩子存在,则把与右孩子结点的连线删除。再查看分离后的二叉树;如果它根节点的右孩子存在,就连线删除。直到所有根节点与右孩子的连线都删除为止。

2)、将每棵分离后的二叉树都转换为树。

步骤如下:

二叉树转化为森林例子

具体实现代码:

//数组实现....森林转成二叉树以及二叉树还原成森林
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#
define N 100
using namespace std;
int mp[N][N];
int pp[N][N];
int n, m;
int ld[N], rd[N], par[N];
void printT(int u)
{
    if (u == 0) return;
    printT(ld[u]);
    printT(rd[u]);
    printf("%d ", u);
}
void rebuildMap(int u, int fa)
{
    if (u == 0) return;
    if (fa != -1) pp[fa][u] = 1;
    rebuildMap(ld[u], u);
    rebuildMap(rd[u], fa); //u节点以及其兄弟节点的父亲节点都是u的父亲节点
}
void buildT(int u)
{
    int v, cur;
    bool flag = false;
    for (v = 1; v <= n; ++v)
        if (mp[u][v])
        {
            if (!flag)
            {
                ld[u] = v;
                cur = v;
                flag = true;
            }
            else
            {
                rd[cur] = v; //将u的兄弟节点都链接在右子树上
                cur = v;
            }
            buildT(v);
        }
}
int main()
{
    while (scanf("%d%d", & n, & m) != EOF)
    {
        memset(par, 0, sizeof(par));
        memset(pp, 0, sizeof(pp));
        memset(mp, 0, sizeof(mp));
        while (m--)
        {
            int u, v;
            scanf("%d%d", & u, & v);
            mp[u][v] = 1;
            par[v] = u;
        }
        int root = -1, cur;
        for (int i = 1; i <= n; ++i)
        {
            if (!par[i])
            {
                if (root != -1) rd[cur] = i;
                if (root == -1) root = i;
                buildT(i);
                cur = i;
            }
        }
        printf("打印树.....
");
        printT(root);
        printf("
");
        rebuildMap(root, -1);
        printf("

还原树....
");
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                if (pp[i][j])
                    printf("%d %d
", i, j);
        printf("KO!
");
    }
    return 0;
}
/*
测试数据.....
8
1
3
4
6
9
7
8
10
*/

以上就是本篇文章的所有内容,二叉树是计算机中不能避免的数据结构,如果还想了解类似java实例问题,就请持续关注奇Q工具网吧。

推荐阅读:

二叉树的遍历图解例题详解

二叉树节点数该怎么计算?有几种算法?

重建二叉树(思路和实现)