Jump to content
  • Advertisement


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


logic for a type of tree?

This topic is 5997 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

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.


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

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!