二叉树【东北大学oj数据结构7-2】C++

二叉树是具有根节点的树，其中每个节点最多具有两个子节点。
您的任务是编写一个程序，读取有根二叉树T并为T的每个节点u打印以下信息：
u的节点ID
u的父节点
u的兄弟节点
u的孩子数量
u的深度
u的高度
节点类型（根节点，内部节点或叶节点）

如果两个节点具有相同的父节点，则它们是兄弟。在这里，如果u和v有相同的父节点，我们说u是v的兄弟姐妹（反之亦然）。
树中节点的高度是从节点到叶子的最长简单向下路径上的边的数量。
这里，给定的二叉树由n个节点组成，每个节点具有从0到n-1的唯一ID。

输入
输入的第一行包含一个整数n，即树的节点数。
在接下来的n行中，每个节点的信息以如下格式给出:
id left right
id为当前节点的id，left为左子节点的id，右为右子节点的id。如果节点没有左(右)子节点，则用-1表示左(右)子节点。

输出
按如下格式打印各节点信息:
node id: parent = p, sibling = s, degree = deg, depth = dep, height = h, type

p是父结点的ID。如果节点没有父节点，则输出-1。
s是其兄弟姐妹的ID。如果该节点没有兄弟节点，则输出-1。
deg、dep、h分别为节点的子节点数、深度和高度。
type是由字符串(根、内部节点或叶)表示的节点类型。如果根可以被认为是一个叶子或内部节点，打印根。
请遵循下面示例输出的格式。

约束
1≤n≤25

输入样例

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

输出样例

node 0: parent = -1, sibling = -1, degree = 2, depth = 0, height = 3, root
node 1: parent = 0, sibling = 4, degree = 2, depth = 1, height = 1, internal node
node 2: parent = 1, sibling = 3, degree = 0, depth = 2, height = 0, leaf
node 3: parent = 1, sibling = 2, degree = 0, depth = 2, height = 0, leaf
node 4: parent = 0, sibling = 1, degree = 2, depth = 1, height = 2, internal node
node 5: parent = 4, sibling = 8, degree = 2, depth = 2, height = 1, internal node
node 6: parent = 5, sibling = 7, degree = 0, depth = 3, height = 0, leaf
node 7: parent = 5, sibling = 6, degree = 0, depth = 3, height = 0, leaf
node 8: parent = 4, sibling = 5, degree = 0, depth = 2, height = 0, leaf 

#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <stdlib.h>
#include <string>
#include <vector>
#include <stack>
#include <queue>

using namespace std;

#define MAX 30

// 定义树的节点结构
struct Node {
    int p, l, r;
};

struct Node T[MAX];  // 树节点数组
int n;  // 节点的数量

int depth[MAX];
int height[MAX];


// 计算树的深度
void calculateDepth() {
    queue<int> q;  // 队列用于BFS
    for (int i = 0; i < n; i++) {
        depth[i] = -1;  // 初始化深度为-1
    }

    // 查找根节点（parent == -1）
    int root = -1;
    for (int i = 0; i < n; i++) {
        if (T[i].p == -1) {
            root = i;
            break;
        }
    }

    // 设置根节点深度为0
    depth[root] = 0;
    q.push(root);

    // BFS遍历树，计算深度
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        // 处理左子节点
        if (T[u].l != -1 && depth[T[u].l] == -1) {
            depth[T[u].l] = depth[u] + 1;
            q.push(T[u].l);
        }

        // 处理右子节点
        if (T[u].r != -1 && depth[T[u].r] == -1) {
            depth[T[u].r] = depth[u] + 1;
            q.push(T[u].r);
        }
    }
}

// 计算树的高度
void calculateHeight() {
    queue<int> q;  // 用队列进行BFS
    vector<int> levelNodes[MAX];  // 存储每一层的节点

    // 查找根节点
    int root = -1;
    for (int i = 0; i < n; i++) {
        if (T[i].p == -1) {
            root = i;
            break;
        }
    }

    // 从根节点开始进行BFS
    q.push(root);
    while (!q.empty()) {
        int u = q.front();
        q.pop();

        levelNodes[depth[u]].push_back(u);  // 按深度存储节点

        // 处理左子节点
        if (T[u].l != -1) {
            q.push(T[u].l);
        }

        // 处理右子节点
        if (T[u].r != -1) {
            q.push(T[u].r);
        }
    }

    // 计算每一层的高度
    for (int i = n-1; i >= 0; i--) {
        for (int u : levelNodes[i]) {
            if (T[u].l == -1 && T[u].r == -1) {
                height[u] = 0;  // 叶子节点的高度为0
            } else {
                int leftHeight = (T[u].l != -1) ? height[T[u].l] : -1;
                int rightHeight = (T[u].r != -1) ? height[T[u].r] : -1;
                height[u] = max(leftHeight, rightHeight) + 1;
            }
        }
    }
}


void print(int u) {

    printf("node %d: ", u);
    printf("parent = %d, ", T[u].p);
    if(T[u].p!=-1)
    {
        int pp=T[u].p;
        if(T[pp].l==u)
        {
            if(T[pp].r!=-1)
            {
                printf("sibling = %d, ",T[pp].r);
            }
            else{
                printf("sibling = -1, ");
            }
        }
        else if(T[pp].r==u)
        {
            if(T[pp].l!=-1)
            {
                printf("sibling = %d, ",T[pp].l);
            }
            else{
                printf("sibling = -1, ");
            }
        }
        else
        {
            printf("sibling = -1, ");
        }
    }
    else
    {
        printf("sibling = -1, ");
    }

    if(T[u].l==-1&&T[u].r==-1)
    {
        printf("degree = 0, ");
    }
    else if(T[u].l!=-1&&T[u].r==-1||T[u].r!=-1&&T[u].l==-1)
    {
        printf("degree = 1, ");
    }
    else
    {
        printf("degree = 2, ");
    }

    int d= depth[u];
    printf("depth = %d, ",d);
    int h=height[u];
    printf("height = %d, ",h);

    if (T[u].p == -1) {
        printf("root\n");
    } else if (T[u].l==-1&&T[u].r==-1) {
        printf("leaf\n");
    } else {
        printf("internal node\n");
    }

}

int main() {
    int i, v, l, r;
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        T[i].p = T[i].l = T[i].r = -1;
        height[i]=-1;
        depth[i]=-1;
    }
    for (i = 0; i < n; i++) {
        scanf("%d %d %d", &v, &l,&r);
        if(l!=-1)
        {
            T[v].l=l;  //一定不可以用i代替v！！！
            T[l].p=v;
        }
        if(r!=-1)
        {
            T[v].r=r;
            T[r].p=v;
        }
    }
    calculateDepth();
    calculateHeight();

    for (int i = 0; i < n; i++) {
        print(i);
    }

    return 0;
}