二叉树是具有根节点的树，其中每个节点最多具有两个子节点。
您的任务是编写一个程序，读取有根二叉树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; // 队列用于BFSfor (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;}}// 设置根节点深度为0depth[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; // 用队列进行BFSvector<int> levelNodes[MAX]; // 存储每一层的节点// 查找根节点int root = -1;for (int i = 0; i < n; i++) {if (T[i].p == -1) {root = i;break;}}// 从根节点开始进行BFSq.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;
}
