Here is some code to study. I should have pointed out that this is
O(n) where n is # of nodes. This leaves out error checking. The
input must be a valid pre-order.
#include <stdio.h>
#include <stdlib.h>
typedef struct node_s {
int key;
struct node_s *left, *right;
} NODE;
void print_tree(NODE *tree)
{
if (tree == NULL) return;
print_tree(tree->left);
printf(" %d", tree->key);
print_tree(tree->right);
}
void save_tree(NODE *tree)
{
if (tree == NULL) return;
printf("%d\n", tree->key);
save_tree(tree->left);
save_tree(tree->right);
}
NODE *new_node(void)
{
int key;
NODE *node = NULL;;
if (scanf("%d", &key) == 1) {
node = malloc(sizeof *node);
node->key = key;
node->left = node->right = NULL;
}
return node;
}
NODE *read_tree(void)
{
int sp = 0;
NODE *root, *new, *current, *parent, *stack[10000];
root = current = new_node();
while ((new = new_node()) != NULL) {
if (new->key < current->key) {
current->left = new;
stack[sp++] = current;
}
else {
parent = current;
while (stack[sp - 1]->key < new->key)
parent = stack[--sp];
parent->right = new;
}
current = new;
}
return root;
}
int main(void)
{
print_tree(read_tree());
return 0;
}
On Oct 18, 10:09 am, Gene <[email protected]> wrote:
> It turns out preorder is enough if you know it was generated from a
> BST. Inorder is needed if it was an arbitrary tree.
>
> One way to code the algorithm is with a stack to hold nodes that
> already have a left child and might still need a right one.
>
> // assume: unique keys
> // root is the tree we're building
> // current is the last node read; invariant is it has no children yet
> // stack S holds nodes with a left child that still might need a
> right.
> // Invariant: top(S) is smallest key in stack
> // and all stacked keys are less than current.
> S = empty
> root = current = new node created from input
> while not end of input {
> p = new node created from input
> if (p->key < current->key) {
> // new node becomes left child of current
> current->left = p;
> // and is now waiting a right child
> push(S, current);
> }
> else {
> // new node is a right child; find its parent:
> // the largest of the set union({current}, S)
> // that is less than current.
> parent = current;
> while (top(S)->key < p->key)
> parent = pop(S);
> // popping has restored stack invariant
> parent->right = p;
> }
> // restore invariant on current
> current = p;
>
> }
>
> On Oct 18, 2:09 am, payal gupta <[email protected]> wrote:
>
>
>
> > hey,i guess a specific binary tree is not possible...by d use of jst a
> > preorder...
> > 4 a specific tree inorder is also reqd...
> > dere will be many trees posible...sso is it dat v got 2 make all possible
> > tree vth d given preorder???
>
> > On Tue, Oct 18, 2011 at 10:12 AM, Ankuj Gupta <[email protected]> wrote:
> > > How to reconstruct a BST from just the prorder traversal of that tree ?
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to [email protected].
> > > To unsubscribe from this group, send email to
> > > [email protected].
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
