Archived

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

The C modest god

Here is a simple yet complex problem...

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
Agony    3452
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
SoulSpectre    169
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
Madhed    4095
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
SporadicFire    162
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   
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