/*/////////////////////////////////////////////////////////////////////////////
//
//	tree.c - a binary tree traversal algorithm demonstration
//
//	©2010 by Josh Moyer <jmoyer@nodomain.net>.  All Rights Reserved.
//
/////////////////////////////////////////////////////////////////////////////*/

#include <stdio.h>

struct n					/* a generic binary tree node */
	{
	int		d;				/* data */
	struct	n *l;			/* left */
	struct	n *r;			/* right */
	};
enum m { IN, POST, PRE };	/* traversal methods */

/*	traverse a binary tree and print each node's value, returning nothing
 *
 *	n: node that search is rooted in
 *	m: one of the traversal methods specified in the t enum
 */
void traverse(struct n *n, enum m m)
	{
	if (m == IN) goto left;
	if (m == POST) goto left;
	if (m == PRE) goto root;

	root:
		printf("%d ",n->d);
		if (m == PRE) goto left;
		if (m == POST) return;
		if (m == IN) goto right;

	left:
		if (n->l != NULL) traverse(n->l, m);
		if (m == PRE) goto right;
		if (m == POST) goto right;
		if (m == IN) goto root;

	right:
		if (n->r != NULL) traverse(n->r, m);
		if (m == IN) return;
		if (m == POST) goto root;
		if (m == PRE) return;
	}

int main()
	{
	/* in-ordered dataset, partial */
	struct n in06 = {  8, NULL,			NULL	};
	struct n in02 = {  1, NULL,			NULL	};
	struct n in01 = {  1, NULL,			NULL	};
	struct n in04 = {  3, NULL,			NULL	};
	struct n in03 = {  2, NULL,			NULL	};
	struct n in05 = {  5, NULL,			NULL	};
	struct n in08 = { 21, NULL,			NULL	};
	struct n in07 = { 13, NULL,			NULL	};
	struct n in10 = { 55, NULL,			NULL	};
	struct n in09 = { 34, NULL,			NULL	};
	struct n in11 = { 89, NULL,			NULL	};
	
	/* pre-ordered dataset */
	struct n pre11 = { 5, NULL,			NULL	};
	struct n pre10 = { 3, NULL,			NULL	};
	struct n pre09 = { 5, &pre10,		NULL	};
	struct n pre08 = { 6, &pre09,		&pre11	};
	struct n pre07 = { 2, NULL,			&pre08	};
	struct n pre06 = { 9, NULL,			NULL	};
	struct n pre05 = { 5, NULL,			NULL	};
	struct n pre04 = { 1, &pre05,		&pre06	};
	struct n pre03 = { 4, NULL,			NULL	};
	struct n pre02 = { 1, &pre03,		&pre04	};
	struct n pre01 = { 3, &pre02,		&pre07	};

	/* post-ordered dataset	*/
	struct n post01 = {   0, NULL,		NULL	};
	struct n post02 = {   1, NULL,		NULL	};
	struct n post03 = {   2, NULL,		NULL	};
	struct n post04 = {   4, NULL,		&post03	};
	struct n post05 = {   8, &post02,	&post04	};
	struct n post06 = {  16, &post01,	&post05	};
	struct n post07 = {  32, NULL,		NULL	};
	struct n post08 = {  64, NULL,		NULL	};
	struct n post09 = { 128, &post07,	&post08	};
	struct n post10 = { 256, &post06,	&post09	};

	/* in-ordered dataset, continued */
	in06.l = &in02;		in06.r = &in08;
	in02.l = &in01;		in02.r = &in04;
	in04.l = &in03;		in04.r = &in05;
	in08.l = &in07;		in08.r = &in10;
	in10.l = &in09;		in10.r = &in11;

	printf("In-order:\t");
	traverse(&in06, IN);
	printf("\n");

	printf("Post-order:\t");
	traverse(&post10, POST);
	printf("\n");

	printf("Pre-order:\t");
	traverse(&pre01, PRE);
	printf("\n");

	return 0;
	}