• Advertisement

Archived

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

Here is a simple yet complex problem...

This topic is 5021 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

Imagine you have a full binary tree. Now number the nodes from top to bottom and from left to right in a row. A numbered tree would look like this: 0 / \ 1 2 / \ / \ 3 4 5 6 Now that you have the tree numbered this way, given a number, how would you get the path reaching that number?

Share this post


Link to post
Share on other sites
Advertisement
all the left nodes of your tree are odd, that might quicken things but a binary search tree would be better.

Share this post


Link to post
Share on other sites
Is this homework? A challenge? Are you just curious?

If it''s something like that latter two, I''m game. ''Cause it''s actually quite simple. It''s a curious question, though, so I''ll be curious first.

Share this post


Link to post
Share on other sites
Smells like homework.

But as a hint trying looking at the binary representation of the node nubmer.

Share this post


Link to post
Share on other sites
this how to find the path:
//x is the number that we want to find the path too.

repeat till x = 0
if(!x%2) x = (x-2)/2 //number is even
else x = (x-1)/2
y[index++] = x

then when you reach 0 you will have the path in the reverse order. Ie from the node in question to the root.

Share this post


Link to post
Share on other sites
We never did find out what it was for...

Share this post


Link to post
Share on other sites
To solve it in a more generic way use recursion.



#include <iostream>

class Node
{
public:
int number;
Node* leftNode;
Node*rightNode;

public:
Node(int num)
{
number = num;
leftNode = 0;
rightNode = 0;
}
Node(Node& l, Node& r, int num)
{
leftNode = &l;
rightNode = &r;
number = num;
}

bool getPath(int n)
{
if (number == n ||
(leftNode && leftNode->getPath(m)) ||
(rightNode && rightNode->getPath(m)))
{
std::cout << number << "->";
return true;
}
else return false;
}
};

int main(void)
{
Node a(Node(Node(Node(3)),Node(Node(4)),1),Node(Node(5),Node(6),2),0);

int x = 3; //Node to find
a.getPath(x);
return 0;
}


I hope that works... took me 3 minutes

(EDIT)
no, now it works... :D
(/EDIT)

--::[Madhed]::--

[edited by - MadHed on May 26, 2004 5:18:08 PM]

Share this post


Link to post
Share on other sites
A tree that is numbered like that and full is a heap. A heap can be represented by an array with certain special properties.
It has to be a 1 indexed array or just waste one element (or the formula gets a little
more complex). But, Node #n is n+1st element of
the array. its children are elements 2n, and 2n+1 which correspond to nodes 2n-1 and 2n. its parent is
element n/2 (integer division) which corresponds to node n/2 -1, . So, to trace back, keep dividing the
node # by 2 until you reach 1. Of course, since your first
node is 0, you have to subtract 1 from each array element # along
the path.

SporadicFire

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Wow, why do y''all keep posting. Anon Mike said all that needed to be said, whether it was for homework or not.

Share this post


Link to post
Share on other sites

  • Advertisement