Thread: Search function for binary tree

  1. #1
    Registered User
    Join Date
    Feb 2018
    Posts
    21

    Search function for binary tree

    Hi again guys,
    I'm back with another question, this time concerning tree structures.
    My tree is a binary tree and the nodes are struct as follows:
    Code:
    struct Node {
        int info;
        struct Node *parent;
        struct Node *right;
        struct Node *left;
    };
    So, I need to write this function Search that return the node required.
    The strategys that I have to use are:
    -Postorder visit
    -Preorder visit
    -Symmetrical
    For now I'm trying to use the first strategy.
    Then, I have already written this two codes both working:
    Code:
    int main(int argc, char **argv) {
        ...
    }
    
    //first node is tree root
    struct Node *Search(struct Node *node, int i) {
        if (!node)
            return NULL;
        if (node->info == i)
            return node;
        struct Node *l = Search(node->left, i);
        struct Node *r = Search(node->right, i);
        if (l)
            return l;
        else
            return r;
    }
    Code:
    bool found = false;
    struct Node *s;
    
    
    int main(int argc, char **argv) {
        ...
    }
    
    //first node is tree root
    void Search(struct Node *node, int i) {
        if (!node)
            return NULL;
        if (node->info == i) {
            found = true;
            s = node;
        }
        if (!found) {
            Search(node->left, i);
            Search(node->right, i);
        }
        found =false;
    }
    The first code is my first implementation, works fine but, is not efficient because even if it find the node, the procedure seems continue until the end of tree.
    So, I've written the 2nd code, that can stops when find the node but it, istead, looks really horrible for me!
    My question is:
    There are other ways more intelligent and more beautiful to see, to implement my 2nd code? Or maybe there are other approaches that I have not considerate?
    Last edited by Jacopo; 02-21-2018 at 04:00 AM.

  2. #2
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Well... I'd normally return the node from Search() if it was found, in which case the code is something like:

    Code:
    int main(int argc, char **argv)
    {
        struct Node tree;
        struct Node *match;
    
    
        ...
            do necessary stuff here to set up tree
        ...
        
        match = Search(&tree, 5); // search for 5
        if (match) {              // if found
           ...
        } else {                  // not found
           ...
        }
    
    
    }
    
    
    struct Node *Search(struct Node *node, int i)
    {
    
        struct Node *match = NULL;
    
        if (!node)
    
            return NULL;
    
    
        if (node->info == i) {
    
            match = node;
    
        } else {
    
            match = Search(node->left, i);
            if (!match)
                     match = Search(node->right, i);
    
        }
    
        return match;
    
    }
    (not tested; typed directly into this message box)
    Last edited by Hodor; 02-21-2018 at 05:47 AM.

  3. #3
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    mh, but the pointer "match" would be always NULL for each call of function, right? So for each call of Search the if condition will be always false and return will be always NULL as well..
    EDIT: Ok, your code works fine, even if I cannot explain how..
    EDIT2: Well, I've understand this code, obviously the pointer do referred at different memory location at each call...I think..
    Last edited by Jacopo; 02-21-2018 at 09:26 AM.

  4. #4
    misoturbutc Hodor's Avatar
    Join Date
    Nov 2013
    Posts
    1,456
    Quote Originally Posted by Jacopo View Post
    mh, but the pointer "match" would be always NULL for each call of function, right? So for each call of Search the if condition will be always false and return will be always NULL as well..
    EDIT: Ok, your code works fine, even if I cannot explain how..
    EDIT2: Well, I've understand this code, obviously the pointer do referred at different memory location at each call...I think..
    Yeah, every time the function is called recursively 'node' is pointing to a different node

    You should also implement the function using the other 2 traversal "orders" to help cement your understanding

  5. #5
    Registered User
    Join Date
    Feb 2018
    Posts
    21
    I'll do it!
    Thank you so much!

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary Search Tree-search method help?
    By shocklightning in forum C++ Programming
    Replies: 5
    Last Post: 03-25-2012, 10:57 PM
  2. Replies: 1
    Last Post: 04-16-2011, 04:44 AM
  3. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  4. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  5. Search Engine - Binary Search Tree
    By Gecko2099 in forum C Programming
    Replies: 9
    Last Post: 04-17-2005, 02:56 PM

Tags for this Thread