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

多叉树定义

有一个根节点多个孩子结点(不止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);
}
1
2
3
4
5
6
7

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

递归求深度复杂度分析

用递归求深度只需要将各个结点遍历一遍所以复杂度为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

输出结点信息