Here is a little program to show how it works. It's a nice little
problem. There is also a coding with recursion.
#include <stdio.h>
#include <stdlib.h>
typedef struct node_s {
int data;
struct node_s *left, *right;
} NODE;
void print_tree(NODE *tree)
{
if (tree == NULL) return;
print_tree(tree->left);
printf(" %d", tree->data);
print_tree(tree->right);
}
void save_tree(NODE *tree)
{
if (tree == NULL) return;
printf("%d\n", tree->data);
save_tree(tree->left);
save_tree(tree->right);
}
NODE *new_node(int data)
{
NODE *node = malloc(sizeof *node);
node->data = data;
node->left = node->right = NULL;
return node;
}
NODE *read_tree(void)
{
int data, sp = 0;
NODE *root, *node, *last, *stack[10000];
// Loop invariants: Root holds tree root.
// Last holds last node added.
// Stack[i] holds the unique node at
// level i to which a right child might
// still be added.
root = last = NULL;
while (scanf("%d", &data) == 1) {
node = new_node(data);
if (root == NULL)
root = node;
else {
// If new node has key < last, it must
// be the left child of last. Attach and
// push onto stack because we still
// may receive a right child.
if (data < last->data) {
last->left = node;
stack[sp++] = last;
}
// Else it has key > last, so if the key is also <
// the deepest level waiting for a right child, it
// can only be right child of the last node.
else if (sp == 0 || data < stack[sp - 1]->data)
last->right = node;
// Else it must be the right child of an ancestor.
// The possible ancestors are on the stack.
// Pop the stack until we find the last ancestor
// with larger key and attach there.
else {
while (sp > 1 && data > stack[sp - 2]->data)
--sp;
stack[--sp]->right = node;
}
}
last = node;
}
return root;
}
int main(void)
{
print_tree(read_tree());
return 0;
}
On Sep 24, 8:28 pm, vikas <[email protected]> wrote:
> if this is simple BST then only preorder will suffice
>
> On Sep 24, 10:16 pm, wetheart <[email protected]> wrote:
>
>
>
> > You can put the array representation of binary tree directly, with
> > some obvious modifications ofcourse :)
>
> > On Sep 24, 5:38 pm, asdqwe <[email protected]> wrote:
>
> > > you can put two traversals of three (inorder, preorder or postorder)
> > > in the file..
> > > Two traversals are enough to dedicate a particular tree.
>
> > > On Sep 24, 4:05 pm, Asit Dhal <[email protected]> wrote:
>
> > > > I need to print a binary search tree in file. When I will retrieve the
> > > > same
> > > > tree from the file.
>
> > > > I have thought about printing in xml format like this
>
> > > > 100
> > > > / \
> > > > 50 150
> > > > / \ / \
> > > > 30 70 120 200
>
> > > > <Level 0>
> > > > 100
> > > > <Level 1>
> > > > 50
> > > > <Level 2>
> > > > 30
> > > > </Level2>
> > > > <Level 2>
> > > > 70
> > > > </Level 2>
> > > > </Level 1>
> > > > <Level 1>
> > > > 150
> > > > <Level 2>
> > > > 120
> > > > </Level 2>
> > > > <Level 2>
> > > > 200
> > > > </level 2>
> > > > </level 1>
> > > > </level 0>
>
> > > > I don't know will this be the best solution or not.
>
> > > > Please suggest me how to approach it or some better solution.
>
> > > > Regards
> > > > Asithttp://kodeyard.blogspot.com/- 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.
