Binarytree.cpp

#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;
}