Search BST without the indexed value...

[Nexgr]

Hello,

I create a bst with the following code:

class BinarySearchTree
{
    public:
        struct tree_node
        {
            string code;
            float min;
            float max;
            tree_node* left;
            tree_node* right;
        };
        tree_node* root;

        BinarySearchTree() {
           root = NULL;}

        bool isEmpty() const { return root==NULL; }

};

The tree is sorted according to the min value, but i want to search the tree with the code value. Obviously i have to check all nodes recursively , and if i found the code i must return two pointers, one for the target node (tree_node* target) and one more for his parent (tree_node* parent).

I am trying to define a function with the following code...

void BinarySearchTree::find(string cod, tree_node* tree, tree_node* target, tree_node* parent, bool& found) {

    if(tree != NULL && !found){

        if(tree->left->code == cod || tree->right->code == cod) {

            parent=tree;
            found = true;

            if (tree->left->code == cod)
                target = tree->left;
            else
                target = tree->right;
        }

        else {
            if(tree->left) find(cod,tree->left,target,parent,found);
            if(tree->right) find(cod,tree->right,target,parent,found);
        }
    }
}

Can you help me, to define the find function ?

Thanks in advance !

[Narue]

target and parent need to be references as well (or pointers to pointers) if you're using them as output parameters:

void find(string cod, tree_node* tree, tree_node*& target, tree_node*& parent, bool& found);

[Nexgr]

Thanks, for your reply.

Yes you are right, i already had & into the two pointers but i copied the code from the old file were missing.

The problem that i have is that the function doesn't search on all right nodes.

It is searching on left nodes, but not on all right nodes :(

Any help ?

[mrnutty]

To transverse the tree and test for certain condition you can a structure like this:

//assume private
template<typename Predicate>
bool MyTree::transverse(const TreeNode& root,const Predicate& tester){
  if(!root) return false;
  else if(tester(root.getCod()) == true) return true;
  else return transverse(root.getLeftChild()) || transverse(root.getRightChild());
}
//assume public
bool MyTree::find(const std::string& target){
 struct MyCompare{
   bool operator()(const std::string& val)const{ return val == target; }
 }
 return this->transverse(this->rootNode , MyCompare);
}

The above is to give you an idea, I make no guarantees!

EDIT: It seems like you also want to store the node if there a match, in that case you can simply change a few things like so.

//assume private
template<typename Predicate>
bool MyTree::transverse(const TreeNode& root,const Predicate& tester){
  if(!root) return false;
  else if(tester(root) == true) return true;
  else return transverse(root.getLeftChild()) || transverse(root.getRightChild());
}
//assume public
bool MyTree::find(const std::string& target){
 struct MyCompare{
   TreeNode* matchNode;
   MyCompare(): matchNode(0){}; //init to 'null'
   bool operator()(const TreeNode& node)const{
     bool res = false;
     if(node.getCod() == target){
       matchNode = &node;
       res = true;
     }
     return res;
   }
 }
 MyCompare comp;
 bool found = this->transverse(this->rootNode , comp);
 if(found){
   /* comp.matchNode */ is valid and is the node that matches the target
 }
 else{ 
  /* no match found */
 }
 return somethingDependingOnAbove;
}

Basically when comparing the predicate, if its true you also save a pointer to that node

[Narue]

Yes you are right, i already had & into the two pointers but i copied the code from the old file were missing.

It couldn't hurt to make sure that your question and code are both up-to-date before posting. Otherwise you cause people to waste their time solving problems that don't exist.

The problem that i have is that the function doesn't search on all right nodes.

Note that you neglected to specify what the problem was in your first post. So don't be surprised that I fixed the most obvious issue.

[Nexgr]

It couldn't hurt to make sure that your question and code are both up-to-date before posting. Otherwise you cause people to waste their time solving problems that don't exist.

Note that you neglected to specify what the problem was in your first post. So don't be surprised that I fixed the most obvious issue.

Sorry my fault, difficult understand such a small difference when you are working under pressure.

Also, i notice that the function works for some left nodes after your post.

[Nexgr]

To transverse the tree and test for certain condition you can a structure like this:

//assume private
template<typename Predicate>
bool MyTree::transverse(const TreeNode& root,const Predicate& tester){
  if(!root) return false;
  else if(tester(root.getCod()) == true) return true;
  else return transverse(root.getLeftChild()) || transverse(root.getRightChild());
}
//assume public
bool MyTree::find(const std::string& target){
 struct MyCompare{
   bool operator()(const std::string& val)const{ return val == target; }
 }
 return this->transverse(this->rootNode , MyCompare);
}

The above is to give you an idea, I make no guarantees!

EDIT: It seems like you also want to store the node if there a match, in that case you can simply change a few things like so.

//assume private
template<typename Predicate>
bool MyTree::transverse(const TreeNode& root,const Predicate& tester){
  if(!root) return false;
  else if(tester(root) == true) return true;
  else return transverse(root.getLeftChild()) || transverse(root.getRightChild());
}
//assume public
bool MyTree::find(const std::string& target){
 struct MyCompare{
   TreeNode* matchNode;
   MyCompare(): matchNode(0){}; //init to 'null'
   bool operator()(const TreeNode& node)const{
     bool res = false;
     if(node.getCod() == target){
       matchNode = &node;
       res = true;
     }
     return res;
   }
 }
 MyCompare comp;
 bool found = this->transverse(this->rootNode , comp);
 if(found){
   /* comp.matchNode */ is valid and is the node that matches the target
 }
 else{ 
  /* no match found */
 }
 return somethingDependingOnAbove;
}

Basically when comparing the predicate, if its true you also save a pointer to that node

Thanks for your reply, i tried to transform your code but i can't.

I am trying with the following code, and the problem is that it only executes the first call on else block which is searching on left nodes. The second call which is searching on the right nodes never executes. Any help why is this happen ?

void BinarySearchTree::find(string cod, tree_node* tree, tree_node*& target, tree_node*& parent, bool& found) {

    if(tree != NULL && !found){

        if(tree->left->code == cod || tree->right->code == cod) {

            parent=tree;
            found = true;

            if (tree->left->code == cod)
                target = tree->left;
            else
                target = tree->right;
            return;
        }

        else {

[B]            if(tree->left!=NULL) find(cod,tree->left,target,parent,found);  //Executes[/B]
            if(tree->right!=NULL) find(cod,tree->right,target,parent,found); //Not execute


        }
    }
}

Edit: If i change the order between the two calls of function find, it executes on for the right nodes, but not in left nodes :S

[nezachem]

I suspect that by "not execute" you mean "crashes before reaching that point".

The reason is that at some point the recursion reaches the leaf node. Such node passes the tree != NULL , after which you dereference tree->left , which is NULL (and never tested against).

[Nexgr]

I suspect that by "not execute" you mean "crashes before reaching that point".

The reason is that at some point the recursion reaches the leaf node. Such node passes the tree != NULL , after which you dereference tree->left , which is NULL (and never tested against).

Exactly, it crashes !

Any idea how can i fix it ?

[Nexgr]

You were right, I fix it !

I changed the condition into the first if as: if(tree != NULL && !found && tree->left != NULL && tree->right != NULL)

I also add two more checks (if the left is null and the right present / if the left is present and the right is null).

Thanks for your help ;-)