aoj

# ALDS1_7_B Tree - Binary Trees

ALDS1_7_B Tree - Binary Trees
Feb. 2, 2020, 1:52 p.m.

## 解答

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #define MAX 100001 #define NIL -1 struct Node { int parent, left, right; }; int degree(int n, Node nodes[]) { if (nodes[n].left != NIL && nodes[n].right != NIL) return 2; if (nodes[n].left == NIL && nodes[n].right == NIL) return 0; return 1; } int sibling(int n, Node nodes[]) { if (nodes[n].parent == NIL) return NIL; int p = nodes[n].parent; if (nodes[p].left == n) return nodes[p].right; return nodes[p].left; } void depth(int n, int d, Node nodes[], int ds[]) { ds[n] = d; if (nodes[n].right != NIL) depth(nodes[n].right, d+1, nodes, ds); if (nodes[n].left != NIL) depth(nodes[n].left, d+1, nodes, ds); } int height(int n, Node nodes[], int hs[]) { int left = 0; int right = 0; if (nodes[n].left != NIL) left = 1 + height(nodes[n].left, nodes, hs); if (nodes[n].right != NIL) right = 1 + height(nodes[n].right, nodes, hs); hs[n] = (left > right) ? left : right; return hs[n]; } void print(int i, Node nodes[], int ds[], int hs[]) { cout << "node " << i << ": "; cout << "parent = " << nodes[i].parent; cout << ", sibling = " << sibling(i, nodes); cout << ", degree = " << degree(i, nodes); cout << ", depth = " << ds[i]; cout << ", height = " << hs[i]; cout << ", "; if (nodes[i].parent == NIL) cout << "root"; else if (nodes[i].left == NIL && nodes[i].right == NIL) cout << "leaf"; else cout << "internal node"; cout << endl; } int main() { int n, id, left, right, root, c; Node T[MAX]; int D[MAX]; int H[MAX]; cin >> n; for (int i=0; i> id >> left >> right; T[id].left = left; T[id].right = right; T[left].parent = id; T[right].parent = id; } for (int i=0; i