Instantly share code, notes, and snippets.

tooshitaka/Binarytree.cpp Created Mar 11, 2017

What would you like to do?
 #include #include #include struct { int parent; int left; int right; } typedef node; using namespace std; const int NIL = -1; node tree[100000]; int D[100000]; int H[100000]; // Calculate depth of nodes void depth(int u, int p) { D[u] = p; if (tree[u].right != NIL) depth(tree[u].right, p + 1); if (tree[u].left != NIL) depth(tree[u].left, p + 1); } // Calculate height of nodes int height(int u) { int h1, h2; h1 = h2 = 0; if (tree[u].left != NIL) h1 = height(tree[u].left) + 1; if (tree[u].right != NIL) h2 = height(tree[u].right) + 1; return H[u] = max(h1, h2); } // MAIN FUNCTION int main(int argc, char** argv) { // Input int n; cin >> n; for (int i = 0; i < n; i++) { tree[i].left = tree[i].parent = tree[i].right = NIL; } int degree; int v; int s; int pre; int l, r; for (int i = 0; i < n; i++) { cin >> v >> l >> r; tree[v].left = l; tree[v].right = r; tree[l].parent = v; tree[r].parent = v; } // Find root int root = 0;; while (tree[root].parent != NIL) { root = tree[root].parent; } // Calculate depth depth(root, 0); // Calculate height height(root); // Output for (int i = 0; i < n; i++) { cout << "node " << i << ":" << " parent = " << tree[i].parent << ", "; // Out put sibling cout << "sibling = "; if (tree[i].parent == NIL) cout << -1; else if (tree[tree[i].parent].left != i) cout << tree[tree[i].parent].left; else cout << tree[tree[i].parent].right; // Output degree cout << ", degree = "; if (tree[i].left != NIL && tree[i].right != NIL) cout << 2; else if (tree[i].left == NIL && tree[i].right == NIL) cout << 0; else cout << 1; // Output depth cout << ", depth = " << D[i]; // Output height cout << ", height = " << H[i]; // Output type of node cout << ", "; if (tree[i].parent == NIL) cout << "root"; else if (tree[i].left == NIL && tree[i].right == NIL) cout << "leaf"; else cout << "internal node"; cout << endl; } return 0; }