多叉树(左孩子右兄弟)详细实现

多叉树定义

有一个根节点多个孩子结点(不止2个孩子结点)

相比于二叉树,只需要写一个结构体,在结构体中添加parent,left,right就可以表示整颗树,但是多叉树有多个孩子结点,无法仅用左右孩子做到!

怎么做呢?

我们利用"左孩子""右兄弟"的定义方法实现多叉树! 我们仍然用一个结构体实现,结构体中仍然是parent,left,right,只不过定义与二叉树不同! 在多叉树中left定义为:一个结点的最左边的孩子结点! 在多叉树中right定义为:一个结点的相邻右侧的兄弟结点!

图示:

结点深度问题(递归实现)

在递归算法中,我们传入结点u,以及深度p,用一个D[i]数组表示i号结点的深度 每次先看u的右兄弟是否存在,如果存在递归调用u.right,传入的深度p不变 如果u的右兄弟不存在,我们调用u.left看u的左孩子是否存在,传入深度p+1! (顺序可以改变,先看左孩子,再看右兄弟也可!)

实现代码

void fd(int u,int p)
{
          
   
    D[u]=p;
    if(T[u].r!=NUL) fd(T[u].r,p);
    if(T[u].l!=NUL) fd(T[u].l,p+1);
}

递归树图解:(按先右兄弟,在左孩子顺序实现)

递归求深度复杂度分析

用递归求深度只需要将各个结点遍历一遍所以复杂度为O(n)

整体代码实现

输入n,总结点数 依次输入结点id,结点的度k,子结点c1,c2,…(有几个子结点,度就为多少) 13 0 3 1 4 10 1 2 2 3 2 0 3 0 4 3 5 6 7 5 0 6 0 7 2 8 9 8 0 9 0 10 2 11 12 11 0 12 0

输出结点信息

#include <bits/stdc++.h>

using namespace std;
const int NUL=-1;
const int maxn=1e5+10;
int n,id,k,c;

struct node
{
          
   
    int p,l,r;
} T[maxn];
int D[maxn];

void init()
{
          
   
    for(int i=0; i<n; i++)
    {
          
   
        T[i].l=T[i].p=T[i].r=NUL;
    }
}

void fd(int u,int d)
{
          
   
    D[u]=d;
    if(T[u].r!=NUL) fd(T[u].r,d);
    if(T[u].l!=NUL) fd(T[u].l,d+1);
}
//打印结点信息
void print(int u)
{
          
   
    cout<<" node"<<u<<": parent = "<<T[u].p<<", depth = "<<D[u];
    if(T[u].p==NUL)
    {
          
   
        cout<<" ,root, [";
    }
    else if(T[u].l==NUL)
    {
          
   
        cout<<" ,leaf, [";
    }
    else
    {
          
   
        cout<<" ,internal node, [";
    }

    for(int i=0,c=T[u].l;c!=NUL;i++,c=T[c].r)
    {
          
   
        if(i)cout<<", ";
        cout<<c;
    }
    cout<<"]"<<endl;

}

int main()
{
          
   

    cin>>n;
    init();//初始化
    int left,parent;
    //读入结点信息
    for(int i=0; i<n; i++)
    {
          
   
        cin>>id>>k;
        for(int j=0; j<k; j++)
        {
          
   
            cin>>c;
            if(j==0)
            {
          
   
                T[id].l=c;
            }
            else
            {
          
   
                T[left].r=c;
            }
            left=c;
            T[c].p=id;
        }
    }
    for(int i=0; i<n; i++)
    {
          
   
        if(T[i].p==NUL)
        {
          
   
            parent=i;
            break;
        }
    }
    fd(parent,0);//递归求深度

    for(int i=0; i<n; i++)//打印n个结点的子节点
    {
          
   
        print(i);
    }

 return 0;
}