?
Solved

Searching a tree

Posted on 2003-03-05
9
Medium Priority
?
264 Views
Last Modified: 2012-05-04
Hi,
If I am given a tree how can I find a path from each node to everyother node?
Thanx,
0
Comment
Question by:psm8780
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
  • 2
  • +3
9 Comments
 

Author Comment

by:psm8780
ID: 8074057
I need answer as soon as possible, plz....
0
 
LVL 2

Expert Comment

by:keenez
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

by:keenez
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
Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
LVL 4

Expert Comment

by:snewo
ID: 8074116

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

0
 
LVL 6

Expert Comment

by:gj62
ID: 8074150
What type of tree is it?
0
 

Accepted Solution

by:
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

by:Linzer
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

by:tox
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

by:psm8780
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

What does it mean to be "Always On"?

Is your cloud always on? With an Always On cloud you won't have to worry about downtime for maintenance or software application code updates, ensuring that your bottom line isn't affected.

Question has a verified solution.

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

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
This tutorial is posted by Aaron Wojnowski, administrator at SDKExpert.net.  To view more iPhone tutorials, visit www.sdkexpert.net. This is a very simple tutorial on finding the user's current location easily. In this tutorial, you will learn ho…
The goal of this video is to provide viewers with basic examples to understand and use pointers in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.
Suggested Courses

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

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

Join & Ask a Question