0 Replies - 1516 Views - Last Post: 03 February 2011 - 04:21 PM Rate Topic: -----

#1 japanir   User is offline

  • jaVanir
  • member icon

Reputation: 1014
  • View blog
  • Posts: 3,025
  • Joined: 20-August 09

Construct a Binary Tree given it's Post Order and In Order Traversals

Posted 03 February 2011 - 04:21 PM

Description: Given 2 arrays representing the binary tree's InOrder and PostOrder traversals, the function constructs and return that binary tree.
//The Tree Node struct:

/*
typedef struct t_node
{
	int data;
	struct t_node *right;
	struct t_node *left;
} tree_node;
*/

tree_node* CreateTreeFromInAndPostOrder(int* post, int* in, int l, int r, int pos){
	if(r < l){
		return NULL;
	}
	else {
		int i;
		tree_node* t = (tree_node*)malloc(sizeof(tree_node));
		t->data = post[pos];
		for(i = l; i < r; i++){
			if(post[pos] == in[i]){
				break;
			}
		}
		t->left = CreateTreeFromInAndPostOrder(post, in, l, i - 1, pos - 1 - (r - i));
		t->right = CreateTreeFromInAndPostOrder(post, in, i + 1, r, pos - 1);
		return t;
	}
}


Is This A Good Question/Topic? 0
  • +

Page 1 of 1