468,248 Members | 1,529 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,248 developers. It's quick & easy.

how to traverse a array represented binary tree using only a father field

How to traverse a binary tree whose nodes only contain a father field. e.g.

struct NodeType {
int data;
int father;
};

A left son's father field has a negative value and right son's father field has +ve value. Absolute value of the father field points to the father of the node.
Such tree can be traversed only in an upward direction but i cannot reach all nodes starting at a leaf. Once all nodes reachable from a leaf are traversed, i get stuck. What i can make out is that while constructing the tree, i will need to keep track of more than just one leaf so that i can traverse all nodes of the binary tree

Want to know an algorthm for this

Am tryng to solve a data-structure exercise in aarom m. tenebaum --5.2.4
Jul 24 '10 #1
6 3787
iohos
45
dis mite be a lengthy solution....... do u need d whole algorithm or just d remedial soln
Jul 25 '10 #2
iohos
45
struct TreeNode
{
struct TreeNode *lgame;
int data;
struct TreeNode *rgame;
};
typedef struct TreeNode TreeNode;
Jul 25 '10 #3
@iohos
Dynamic representation is not to be used.

struct NodeType {
int data;
int father;
};

How to traverse a binary tree wherein each node is as shown above

Initial problem specification is to convert a binary tree represented using nodeType as i have shown to a binary tree using nodeType as you have shown.
Jul 25 '10 #4
iohos
45
ok, wrking on it. will post it soon
Jul 25 '10 #5
jkmyoung
2,057 Expert 2GB
  1. Create a node array of same length as your initial array.
  2. For each array element, create a node. Set the values to be the same, but initially set all children to null.
  3. Go back through the array.
  4. Set each node's children accordingly. Eg, if the first array with your NodeType is A, and the second array with the other node is A2:
foreach node in A
{
get parent index
determine if we are left or right child by comparing values.
set A2[parent_index] corresponding child accordingly.
}
Jul 29 '10 #6
hi jkm,
thank u for the solution. its simple & good.

sorry abt the delayed response

Regards
Aug 22 '11 #7

Post your reply

Sign in to post your reply or Sign up for a free account.

Similar topics

7 posts views Thread by pembed2003 | last post: by
reply views Thread by Reed | last post: by
5 posts views Thread by pembed2003 | last post: by
10 posts views Thread by Aris | last post: by
4 posts views Thread by Anthony Liu | last post: by
4 posts views Thread by hankssong | last post: by
1 post views Thread by anarghya | last post: by
4 posts views Thread by whitehatmiracle | last post: by
8 posts views Thread by perdoname | last post: by
reply views Thread by NPC403 | last post: by
reply views Thread by kermitthefrogpy | last post: by
reply views Thread by zattat | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.