Tree help

[spaceman]

Hey guys im having trouble traversing a tree. The assignment is to decode morse code. I have the tree built, but its the search im having trouble with.

i can get the search to work if i use recursion, but the problem is when i cout, i of course get all the values that i have searched through. heres the recursion code and what happens.

 void Search (char code[], BinaryTree& tree, int count)
{
//BinaryTree temptree;
char node;

if (code[count] == '-')
{
Search (code, tree.getRightSubtree(), count + 1);
}

else if (code[count] == '.')
{
Search (code, tree.getLeftSubtree(), count + 1);
}
node = tree.getRootData();
cout << node << endl;
}

if i type in for instance --.-
i will get

Q
G
M
T
'\0' <--- empty space

Q is the right output, but im getting all the other values it searched through



i tried a for loop, but the problem then is it doesn't traverse the tree. If i try to go left, it does, but then it resets back to the root, so im basically going in a circle.

for (count = 0; code[count] == '-' || code[count] == '.'; count++)
{
if (code[count] == '-')
{
tree.getRightSubtree();
}

else if (code[count] == '.')
{
tree.getLeftSubtree();
}
}

node = tree.getRootData();
cout << node << endl;     

so if i entered --- i would simply get 3 empty spaces being '\0' which is my root.

'\0' <----  empty space
'\0' <----  empty space
'\0' <----  empty space

So my question is, is there a way to get the last value outputted from a recursive call?

And any way to get it to work using the for loop?

[mik2718]

how about this?

void Search (char code[], BinaryTree& tree, int count)
{
  //BinaryTree temptree;
  char node;

  if (code[count] == '-')
  {
    Search (code, tree.getRightSubtree(), count + 1);
  }
  else if (code[count] == '.')
  {
    Search (code, tree.getLeftSubtree(), count + 1);
  }
  else
  { // output only when end of string is reached
    node = tree.getRootData();
    cout << node << endl;
  }
}

[spaceman]

yeah thanks, figured it out later that i need a base case, did this instead

void Search (char code[], BinaryTree& tree, int count, char& store)
{
char node;

if (code[count] == '-')
{
Search (code, tree.getRightSubtree(), count + 1, store);
}

else if (code[count] == '.')
{
Search (code, tree.getLeftSubtree(), count + 1, store);
}

else if (code[count] != '-' || code[count] != '.')
{
node = tree.getRootData();
cout << node;
store = node;
}
}

the char& store is irrelevant just something i added, but otherwise it works thanks

[spaceman]

just for curiosity sake, is there any way to get the search to work with the for loop without using recursion?

[mmay]

Yes, but it's not as elegant. You would need to store some idea of the "current" location in the tree, and update this location as you move to the next element of code[].

[naraku9333]

I like elegant code a much as the next guy, but I would definitely sacrifice elegance for speed.

[mmay]

Given the speed of modern CPUs these days, I'm not too sure whether it would be faster or not. All we're doing is saving the "cost" of a recursive call... (note, the following is a cut-down example only which "knows" only two letters, and I had to twist the BinaryTree interface into something more convenient for quick initialisation - spaceman, stick with your own implementation (^_^)h).

#include <iostream>
#include <cstring>

class BinaryTree {
  public:
    BinaryTree( char leaf )
      : data( leaf ), left( NULL ), right( NULL ) {};
    
    BinaryTree( BinaryTree *l, BinaryTree *r )
      : data( 0 ), left( l ), right( r ) {};
    
    char         getRootData() { return data; };
    BinaryTree * getLeftSubtree() { return left; };
    BinaryTree * getRightSubtree() { return right; };

  private:
    char         data;
    BinaryTree * left;
    BinaryTree * right;
};



int
main( int ac, char *av[] )
{
  BinaryTree s( 's' );
  BinaryTree o( 'o' );

  BinaryTree empty( ' ' );
  BinaryTree dots( &s, &empty );
  BinaryTree dotdots( &dots, &empty );
  BinaryTree dasho( &empty, &o );
  BinaryTree dashdasho( &empty, &dasho );
  BinaryTree tree( &dotdots, &dashdasho );

  const char sos[] = "...---...";

  BinaryTree *tmp = &tree;
  for ( unsigned int pos = 0; pos < strlen( sos ); pos++ ) {
    if (sos[pos] == '.') {
      tmp = tmp->getLeftSubtree();
    } else if (sos[pos] == '-') {
      tmp = tmp->getRightSubtree();
    }
    
    // if we're at a leaf node, then print character and return to top of tree
    if (tmp->getLeftSubtree() == NULL && tmp->getRightSubtree() == NULL) {
      std::cout << tmp->getRootData();
      tmp = &tree;
    }
  }

  std::cout << std::endl;
  
  return 0;
}

[naraku9333]

A recursive call isn't expensive, but due to the nature of recursion you are likely to have many recursive calls which can be very expensive. We did timings of Binary Tree searches in CS2, I dont remember the results but I do recall the differences being significant.