Archived

This topic is now archived and is closed to further replies.

Buzz1982

logic for a type of tree?

Recommended Posts

Hi, i want to make a binary tree such that the first item i take as input should create the root of the tree.the 2nd input should be placed as a left child of that root,3rd input as right child,4th as the left child of fisrt left child,5th as the right child of first left child,6th as the left of first right child and 7th as the right child of first right child,u know what i m try to say.if any one can give me the logic please reply. here is the pattern and the input sequence is a,b,c,d,e,f,g. a b c d e f g

Share this post


Link to post
Share on other sites
I think you need a queue-structure, i.e. a FIFO (first-in-first-out) structure. You put stuff on top and get them from bottom.

Steps to do what you want:

0. add 'a' to queue (that is, the root node)

1. get a node from queue
2. place the next 2 characters from the input sequence as this node's children, and also put them to queue
3. start again from step 1

That's it. 'a' will get 'b' and 'c' as children, and 'b' and 'c' will be put to queue. Now queue has 'b' and 'c'. Then 'b' will be "popped" from queue and 'd' and 'e' will be placed as it's children and put in queue. Now queue has 'c', 'd' and 'e'. Then "pop" 'c' from the queue and place 'f' and 'g' as it's children.

[edited by - civguy on July 16, 2002 10:26:36 AM]

Share this post


Link to post
Share on other sites
What you''re describing can be implemented as a simple array
or vector.

In fact, this is how you''d make a binary tree without
using pointers (left, right). All you need is a pair
of suitable functions that return the left child and
the right child.


  
int Tree[1024];

int LeftChild(int Index)
{ return (Index + 1) * 2 - 1; }

int RightChild(int Index)
{ return (Index + 1 ) * 2; }
// end



How do you use it? Just store your inputs sequentially in
the array. Index 0 is the ROOT of the tree. To find
the left child of any index, just use the LeftChild()
function. Similarly for the right child.

Example:

  
Tree[0] = 15;
Tree[1] = 29;
Tree[2] = 55;
Tree[3] = 67;
Tree[4] = 1111;
Tree[5] = 23;
Tree[6] = 3;

cout << Tree[LeftChild(0)]; // Should print 29

cout << Tree[RightChild(2)]; // Should print 3

cout << Tree[LeftChild(LeftChild(0))]; // Should print 67

// And so on



Add in the appropriate error checking and you''re set. That
is an exercise for the reader.


~~~~
Kami no Itte ga ore ni zettai naru!

Share this post


Link to post
Share on other sites