一般树转二叉树

· · 个人记录

一般树转二叉树

实现方法

一般树转二叉树，6字口诀：左儿子，右兄弟

实现步骤

1、将树的根节点直接作为二叉树的根节点

2、将树的根节点的第一个子节点作为根节点的左儿子，若该子节点存在兄弟节点，则将该子节点的第一个兄弟节点（方向从左往右）作为该子节点的右儿子

3、将树中的剩余节点按照上一步的方式，依序添加到二叉树中，直到树中所有的节点都在二叉树中

实际上就是每个点的左儿子是它第一个儿子，右儿子是它从左往右数的第一个兄弟

还可以这样理解普通树转换成二叉树

在所有兄弟结点之间加一连线。对每个结点，除了保留与其第一个儿子的连线外，去掉该结点与其它孩子的连线

代码

#include<bits/stdc++.h>
using namespace std;
const int N=105;

int son[N],left[N],right[N];

int main()
{
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);      //x是i号节点的父亲 
        if(!son[x])  
          left[x]=i;      //这两步就是根据左儿子右兄弟的方式转二叉树 
        else  
          right[son[x]]=i;
        son[x]=i;
    }
    for(int i=1;i<=n;i++)
      printf("%d %d\n",left[i],right[i]);
    return 0;
}

作用

使一些问题（例如树形DP）更方便做