TreeTraversal.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[10000];
int D[10000];
int H[10000];

// 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);
}

// Preorder traversal
void preorder(int u)
{
	cout << " " << u;
	if (tree[u].left != NIL)
		preorder(tree[u].left);
	if (tree[u].right != NIL)
		preorder(tree[u].right);
}

// Inorder traversal
void inorder(int u)
{
	if (tree[u].left != NIL)
		inorder(tree[u].left);
	cout << " " << u;
	if (tree[u].right != NIL)
		inorder(tree[u].right);
}

// Postorder traversal
void postorder(int u)
{
	if (tree[u].left != NIL)
		postorder(tree[u].left);
	if (tree[u].right != NIL)
		postorder(tree[u].right);
	cout << " " << u;
}

// 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;
	}
	
	// Preorder traversal
	cout << "Preorder" << endl;
	preorder(root);
	cout << endl;

	// Inorder traversal
	cout << "Inorder" << endl;
	inorder(root);
	cout << endl;

	// Postorder traversal
	cout << "Postorder" << endl;
	postorder(root);
        cout << endl;
	
	// 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;
}