Solved

# Searching a tree

Posted on 2003-03-05
Medium Priority
271 Views
Hi,
If I am given a tree how can I find a path from each node to everyother node?
Thanx,
0
Question by:psm8780
• 2
• 2
• 2
• +3

Author Comment

ID: 8074057
I need answer as soon as possible, plz....
0

LVL 2

Expert Comment

ID: 8074087
I'm not quite sure of your question.....

Usually you start at the top of a tree.

Are you saying you start at a leaf node, and you have to traverse every possible node in the tree?  (in which case you'll need a pointer "upwards" as well.  Are you looking for shortest distance???

Obviously, trees work with recursive algorithms.  Could you give some more details.

Cheers,

keenez
0

LVL 2

Expert Comment

ID: 8074095
BTW .... since this sounds like homework ... we can only give you some pointers but we won't do it for you.

Keenez
0

LVL 4

Expert Comment

ID: 8074116

And we want 10 points of your grade to come to us.

0

LVL 6

Expert Comment

ID: 8074150
What type of tree is it?
0

Accepted Solution

tox earned 1500 total points
ID: 8074809
Hi,

I assume that your tree structure is a binary tree, i.e., every tree node has two pointers to its left and right children;

Also I interpret your question as a path-finding problem. Here's a sample structure:

A
/    \
B      C
\    / \
F  D  E

Now we want to find the path from F to D, so the output should be F->B->A->C->D

First of all, let's define a tree node as such:

struct TREENODE{
unsigned char nodename;
TREENODE *left;
TREENODE *right;
TREENODE *parent; //this pointer is very important!
}; //i'm not sure if you can get this compiled in a standard C compiler; too much C++ writing these days ;)

Now it's time to construct a crawling bot. After you create the tree, make another node pointer:
TREENODE *bot;

and the following recursive function teaches the bot what to do:

int Move(TREENODE *cur,int caller){
bot=cur;
found=0;
if (bot->nodename==destname) return 1;

switch (caller) { //to prevent loopback
case 1: //call as parent
if ((bot.left==null)&&(bot.right==null))
return 0;
found++=Move(bot.left,2);
found++=Move(bot.right,3);
break;
case 2: //call as left child
if ((bot.parent==null)&&(bot.right==null))
return 0;
found++=Move(bot.parent,1);
found++=Move(bot.right,3);
break;
case 3: //call as right child

if ((bot.left==null)&&(bot.parent==null))
return 0;
Move(bot.parent,1);
Move(bot.left,2);
break;
}//switch
if (found>0) printf("<-%c",bot.nodename);
}//Move

In addition, you have to locate the starting node by a simple recursive search from the root, and put the desination nodename to the global variable "destname".

Finally in the main function,

void main(){
//... a lot of stuff is omitted here

printf("%c",destname);
//the last stop won't be displayed
//so we have to do it manually

Move(bot.left,1);
Move(bot.right,1);
Move(bot.parent,2);
Move(bot.parent,3);
//IMPORTANT: This is the first step of your trying'n'erring. there may be a lot of mistakes in this sample program (especially in the main program) as i am just trying to illustrate the logical structure of my solution

}

As you may see, the output (if this program works) is not F->B->A->C->D, but D<-C<-A<-B<-F instead. You can manipulate the output string if you have time after fixing all the errors in this program. =)

Good luck!
0

LVL 1

Expert Comment

ID: 8076037
tox, if you had read what keenez said, you'd know you're not supposed to completely solve homework problems in here.
0

Expert Comment

ID: 8080273
Let me assume now that you know how to find the path from one node to another node. What you need to find EVERY path is to put a complete traversal result to a list and duplicate this list. Say you've got a preorder list of a,b,c,d , so the second list is also a,b,c,d. The number of paths here are 4*(4-1)=12. Parse the enumerated p2p parameters to the node-to-node finder, and there you go.

To Linzer and Keenez:
Hi, thanks for pointing it out that no homework solutions should be provided here. I'll pay more attention to such things from now on.

0

Author Comment

ID: 8082024
Hey, this was not exactly a homework. Actually I am supposed to be working on this project where I have to find a link carrying maximum traffic in a telecom network. For this I needed a faster solution than DFS to traverse a tree; since my algorithm is getting into cubic running time. Anyway, I did not ask you to do my homework. I just needed an algorithm faster that DFS. But thanx neway....I am accepting tox's answer though it does not solve my problem!!! The reason is I found out from my tacher that its ok to have cubic running time!!!!
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Have you thought about creating an iPhone application (app), but didn't even know where to get started? Here's how: ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ Important pre-programming comments: Iâ€™ve never triâ€¦
Examines three attack vectors, specifically, the different types of malware used in malicious attacks, web application attacks, and finally, network based attacks.  Concludes by examining the means of securing and protecting critical systems and infâ€¦
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand and use while-loops in the C programming language.
###### Suggested Courses
Course of the Month9 days, 19 hours left to enroll

#### 569 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.