树结构是一种数据结构，它由节点（node）以及连节点的边（edge）构成。
如果一棵树具有一个叫为根(root)的特殊节点，那么这棵树称作有根数（rooted tree）。
树结构有如下的定义：
没有子节点的节点称为外部节点（external node）或叶节点（leaf）
除叶节点以外的节点称为内部节点（internal node）
节点x的子节点树称为x的度（degree）
从根r到节点x的路径长度称为x的深度（depth）
节点x到叶节点的最大路径长度称为节点x的高度（height）
不难看出，一棵树中根节点的高度最大，称其为树的高。
二叉树的定义:拥有一个根节点，所有节点的子节点不超过2的树称为二叉树。
#include <iostream> #include <cstdio> using namespace std; const int MAX = 100000; const int NIL = -1; struct Node{ //使用结构体储存 int parent,left,right; }; Node T[MAX]; int n,D[MAX],H[MAX]; void SetDepth(int u,int d){ //递归求深度 if(u==NIL) return; D[u] = d; SetDepth(T[u].right,d+1); SetDepth(T[u].left,d+1); } int SetHeight(int u){ //递归求高度 int h1 = 0,h2 = 0; if(T[u].left != NIL) h1 = SetHeight(T[u].left)+1; if(T[u].right !=NIL) h2 = SetHeight(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 != u &&T[T[u].parent].right != NIL) return T[T[u].parent].right; if(T[T[u].parent].right != u &&T[T[u].parent].left != NIL) return T[T[u].parent].left; } void print(int u){ //输出 printf("node %d: ",u); printf("parent = %d, ",T[u].parent); printf("silbing = %d, ",GetSibling(u)); int beg = 0; if(T[u].left!= NIL) beg++; if(T[u].right != NIL) beg++; printf("degree = %d, ",beg); printf("depth = %d, ",D[u]); printf("height = %d, ",H[u]); if(T[u].parent == NIL) printf("root\n"); else if(T[u].left == NIL &&T[u].right == NIL) printf("leaf\n"); else{ printf("internal node\n"); } } int main() { cin>>n; int v,l,r,root = 0; for(int i =0;i<n;i++){ cin>>v>>l>>r; T[v].left = l; T[v].right = r; if(l!=NIL) T[l].parent = v; if(r!=NIL) T[r].parent = v; } for(int i =0;i<n;i++) if(T[i].parent == NIL) root = i; SetDepth(root,0); SetHeight(root); for(int i = 0;i<n;i++) print(i); return 0; } /* input: 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 */ /* output node 0: parent = 0, silbing = 4, degree = 2, depth = 0, height = 3, internal node node 1: parent = 0, silbing = 1, degree = 2, depth = 0, height = 1, internal node node 2: parent = 1, silbing = 2, degree = 0, depth = 0, height = 0, leaf node 3: parent = 1, silbing = 3, degree = 0, depth = 0, height = 0, leaf node 4: parent = 0, silbing = 4, degree = 2, depth = 0, height = 2, internal node node 5: parent = 4, silbing = 5, degree = 2, depth = 0, height = 1, internal node node 6: parent = 5, silbing = 6, degree = 0, depth = 0, height = 0, leaf node 7: parent = 5, silbing = 7, degree = 0, depth = 0, height = 0, leaf node 8: parent = 4, silbing = 8, degree = 0, depth = 0, height = 0, leaf */