Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
#include <iostream>
#include <algorithm>
#include <string>
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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment