Jump to content
  • Advertisement

Archived

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

The C modest god

Here is a simple yet complex problem...

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

  • Advertisement
×

Important Information

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

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!