Binary Tree from preorder traversal

aksgh

Hi, I have a tree such that it can be uniquely determined from its preorder.I have information on which are internal nodes and which are leaves.Something like this ----0 ----/-\ ---0--0 --/-\--/-\ -1--0-1--1 ----/-\ ----1--1 the preorder being 001011011 I need some logic to get the tree structure from this preorder

Malli_S

Following is not the full fleshed code, it's just a skeletal that gives you an idea for implementation (as u just asked for logic ;) ). Better you implement the rest of the part.

class node
{
node *m_pLeftNode;
node *m_pRightNode;

int m\_iData;

public :

PostOrderTravarse()
{
	m\_pLeftNode->PostOrderTravarse();	//Travarse the right tree
	m\_pRightNode->PostOrderTravarse();	//Travarse the left tree

	cout<<m\_iData; 				// Visiting Node;
}	

PreOrderTravarse()
{
	cout<<m\_iData; 				// Visiting Node;

	m\_pLeftNode->PreOrderTravarse();	//Travarse the right tree
	m\_pRightNode->PreOrderTravarse();	//Travarse the left tree
}	

InOrderTravarse()
{
	m\_pLeftNode->InOrderTravarse();		//Travarse the right tree
	cout<<m\_iData; 				// Visiting Node;
	m\_pRightNode->InOrderTravarse();	//Travarse the left tree
}

};

All the best !

-Malli...! :rose:****

aksgh

ummmm...those are tree traversals I need to construct my tree FROM a preorder traversal

oobimoo

You may get the same sequence from different binary trees. So its not possible.

Malli_S

Yup ! I agree with you, one can't get the same by rebuilding the tree from traversals.

-Malli...! :rose:****

aksgh

Not trying the be bossy or rude...but please look at my question...my tree CAN be uniquely determined from the preorder because I have information about internal nodes and leaves.Its a huffman tree.

oobimoo

aksgh wrote:

Its a huffman tree.

Yes didnt see that, you are right. So, for a huffman tree you could the following

typedef struct _node_info {
int is_leaf;
char value;
}node_info;

typedef struct _node {
node_info inf;
node* l;
node* r;
} node;

// returns the root of the tree, from an array of node_info's structs, that
// represents the preorder traversal of the huffman tree. we assume a global stack s
// initially empty
node* built_tree(node_info* preorder_array, int preorder_array_size)
{
node *root, *n;
int i;
root = malloc(sizeof(node));
stack_push(s, root);
for (i = 0; i < preorder_array_size; i++) {
assert(!stack_empty(s));
n = stack_pop(s);
n->inf = preorder_array[i];
if (!n->inf.is_leaf) {
n->r = malloc(sizeof(node));
stack_push(s, n->r);
n->l = malloc(sizeof(node));
stack_push(s, n->l);
}
}
assert(stack_empty(s));
return root;
}

* i dont set r,l members to zero when i create a node, in order to save some space, but it is something you must do

modified on Friday, September 19, 2008 8:09 AM