二叉树的表达（打印各个节点的详细信息）

给定n，接下来n行每行给出一组节点编号 左子节点编号 右子节点编号 没有子节点用-1表示

输出每个节点的编号，父节点编号，兄弟节点编号，子节点数，深度，高，以及接节点类型

例如：

<mark>关键看：二叉树的存储，高度和深度的递归解决流程</mark>

#include <iostream>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
typedef long long ll;
#define maxn 1000005
#define mod 7654321
#define NIL -1

struct Tree
{
    int parent,left,right;
}T[maxn];

int D[maxn],H[maxn];

//得到u节点的深度，传入根节点，递归解决每个节点的深度
//递归到底部结束，递归过程中存储深度
void getDepth(int u,int d)
{
    if(u==NIL)//退出递归条件
        return;

    D[u]=d;//存储当前节点的深度
    getDepth(T[u].left,d+1);
    getDepth(T[u].right,d+1);
}

//得到u节点的高度,为左右子树中更高的值
//递归到最底部开始往回走走一步加个一得到当前节点的深度存储到H[u]
int getHeight(int u)
{
    int h1=0,h2=0;
    if(T[u].left!=NIL)
        h1=getHeight(T[u].left)+1;
    if(T[u].right!=NIL)
        h2=getHeight(T[u].right)+1;

    return H[u]=(h1>h2?h1:h2);
}

//找兄弟节点
//两种情况，要么没有 兄弟，要么只有一个兄弟
int getSibling(int u)
{
    if(T[u].parent==NIL)//针对根节点，没有兄弟
        return NIL;
    if(T[T[u].parent].left!=NIL&&T[T[u].parent].left!=u)
        return T[T[u].parent].left;
    if(T[T[u].parent].right!=NIL&&T[T[u].parent].right!=u)
        return T[T[u].parent].right;
    //没有左或右兄弟，返回NIL
    return NIL;
}

//打印节点的信息
void print(int u)
{
    printf("node %d: ",u);
    printf("parent = %d, ",T[u].parent);
    printf("sibling = %d, ",getSibling(u));

    //计算子节点数目
    int deg=0;
    if(T[u].left!=NIL) deg++;
    if(T[u].right!=NIL) deg++;
    printf("degree = %d, ",deg);

    printf("depth = %d, ",D[u]);

    printf("height = %d, ",H[u]);

    if(T[u].parent==NIL)
        cout<<"root"<<endl;
    else if(T[u].left==NIL&&T[u].right==NIL)
        cout<<"leaf"<<endl;
    else
        cout<<"internal node"<<endl;
}

int main()
{
    int value,l,r,root=0;
    int n;
    cin>>n;

    //父节点的初始化
    for(int i=0;i<n;i++) T[i].parent=NIL;

    //结构体数组存储
    for(int i=0;i<n;i++)
    {
        cin>>value>>l>>r;
        T[value].left=l;
        T[value].right=r;
        if(l!=NIL) T[l].parent=value;
        if(r!=NIL) T[r].parent=value;
    }

    //查找根节点
    for(int i=0;i<n;i++)
        if(T[i].parent==NIL)
            root=i;
    
    //求各个节点的深度和高度
    //深度：根到当前节点的长度 递归到叶节点结束
    //高度：当前节点到叶节点的最大长度 递归到叶节点再回到起始
    getDepth(root,0);
    getHeight(root);

    //打印各节点信息
    for(int i=0;i<n;i++) print(i);

    return 0;
}