Thread: Given two binary search trees, write a function which.....

  1. #1
    Registered User
    Join Date
    Jun 2019
    Posts
    33

    Given two binary search trees, write a function which.....

    Hi everyone!

    I'm having some troubles with the definition of a function.
    Here there is the exercise:

    "Given two Binary Search Trees, T1 and T2, which contain float values, write a function that create a new Binary Search Tree, which has in his nodes the common elements among T1 and T2".

    This were my thoughts:

    -I create a function which put in an array the elements of a Binary Search Tree (I called it "visitcopy");
    -I create two arrays, A1 and A2, for the values of my T1 and T2;
    -I create a doublepointer and a pointer to a structured data "struct btree" (this is my new Tree);
    -With a for cycle, I make a comparison between the two arrays and everytime I find a common element, I add a node in my new Binary Search Tree.

    Here there is my code:

    Code:
    void newcommon (struct btree *p, struct btree *punt, int first, int second){
    
    //first and second are the number of nodes of the first and second tree
        
        float *A;
        A= (float*)calloc(first, sizeof(float));
        int *k;
        int u=-1;
        k=&u;
            visitcopy(p, A, k);
    
    
        float *B;
        B=(float*)calloc(second, sizeof(float));
            visitcopy(punt, B, k);
    
    
        struct btree **doublepointer;
        struct btree *pointer;
        doublepointer= &pointer;
        init(doublepointer);
    
    
    
    
        int i,j;
        for (i=0;i<first;i++){
            for (j=0;j<second;j++){
                if (A[i]==B[j]){
    
    
                insert_inorder(doublepointer, A[i]);
                printf ("\n\n new node created in the new tree %f\n\n", A[i]);
    
    
                }
            }
        }
    }
    
    
    
    
    void visitcopy (struct btree * ptr, float *E, int *i) {
    
        if (ptr != NULL) {
    
    
            visitcopy(ptr->left_ptr, E, (int)(*i)++);
            E[(*i)]=(ptr->value);
            printf ("\n\n\n  the value number %d of the array is %f  \n\n\n",(*i), E[(*i)]);
    
    
            visitcopy(ptr->right_ptr, E, (int)(*i)++);
        }
    }

    From the debugging, I think that the main problem is in visitcopy, but there are also one or more mistake in the main function.

    Can anyone help me please?

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,086
    Quote Originally Posted by letthem
    -I create a function which put in an array the elements of a Binary Search Tree (I called it "visitcopy");
    -I create two arrays, A1 and A2, for the values of my T1 and T2;
    -I create a doublepointer and a pointer to a structured data "struct btree" (this is my new Tree);
    -With a for cycle, I make a comparison between the two arrays and everytime I find a common element, I add a node in my new Binary Search Tree.
    Don't do that. Binary search trees can be traversed and searched. Traverse over one binary search tree and search the other for its elements, inserting into a third binary search tree each element's value for which there is a match.

    If you really want to go with two arrays, then you might as well assume that the binary search trees have degraded into linked lists, so you sort each array then do a single pass to extract the common values. However, you need to take care when constructing the new binary search tree that you don't create one that degrades into a linked list.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post
    Traverse over one binary search tree and search the other for its elements, inserting into a third binary search tree each element's value for which there is a match.
    Hello Laserlight!

    Unfortunately, I'm not able to do that.
    I know how to do visit a binary search tree (in many ways).
    I know how to search a value in a binary search tree.
    But I'm not able (at all) to do what you wrote.

    May you let me see how you would do that please?

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,086
    Quote Originally Posted by letthem
    I know how to search a value in a binary search tree.
    Write a function to do this. The function will return true if the value is found, otherwise it will return false.

    You can then write another function to visit one of the binary trees and call that function.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    Jun 2019
    Posts
    33
    Quote Originally Posted by laserlight View Post
    Write a function to do this. The function will return true if the value is found, otherwise it will return false.

    You can then write another function to visit one of the binary trees and call that function.
    Hello Laserlight!

    Here there is the function which search a specific value in a Binary Search Tree:

    Code:
    Booleansearch(structbtree* ptr, floattarget) { if(ptr != NULL) { //It's not a leave if(ptr->value== target) { //FOUND returnTRUE;} else{ // NONtrovato if(target < ptr->value)// vaia sx returnsearch(ptr->left_ptr,target); else// oppurevaia dx returnsearch(ptr->right_ptr,target); } } else return FALSE;}
    Let me see if I understood what you said.
    You're suggesting to:
    1)visit the first binary search tree;
    2)use the search function in the second binary search tree for every value of the first binary search tree ;
    3) if the search function give as result TRUE, create a new node in the third tree.

    Am I correct?
    Last edited by letthem; 07-24-2019 at 04:16 AM.

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    27,086
    Yes.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binary search trees
    By Rhaenyx in forum C Programming
    Replies: 1
    Last Post: 05-14-2016, 04:22 AM
  2. Search and delete function for binary trees.
    By nslice22 in forum C Programming
    Replies: 1
    Last Post: 04-01-2014, 03:03 AM
  3. A Binary Search Tree of... Binary Search Trees...
    By SlyMaelstrom in forum C++ Programming
    Replies: 5
    Last Post: 12-10-2005, 02:12 PM
  4. binary search trees
    By sweets in forum C++ Programming
    Replies: 3
    Last Post: 04-05-2004, 11:02 AM
  5. binary search trees
    By student2005 in forum C++ Programming
    Replies: 2
    Last Post: 03-17-2004, 08:49 PM

Tags for this Thread