Like Tree3Likes
  • 1 Post By std10093
  • 2 Post By iMalc

Merging binaries trees into another one

This is a discussion on Merging binaries trees into another one within the C Programming forums, part of the General Programming Boards category; Good evening. I'm studying merging of two binaries trees and I was concerned about two instructions: Code: bitree_root(merge)->left = bitree_root(left); ...

  1. #1
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193

    Question Merging binaries trees into another one

    Good evening. I'm studying merging of two binaries trees and I was concerned about two instructions:

    Code:
    bitree_root(merge)->left = bitree_root(left);
    bitree_root(merge)->right = bitree_root(right);
    I would like to know if merging two binaries trees means to create one of the subtrees as the left node of the new (merged) binary tree and the other as the right node of it.

    Like this (please toggle to plain text):

    Code:
            root of merged tree
               /             \ 
              /               \ 
    left subtree           right subtree
    Code:
     
    int bitree_merge(BiTree *merge, BiTree *left, BiTree *right, const void
       *data) {
    
    /*****************************************************************************
    *                                                                            *
    *  Initialize the merged tree.                                               *
    *                                                                            *
    *****************************************************************************/
    
    bitree_init(merge, left->destroy);
    
    /*****************************************************************************
    *                                                                            *
    *  Insert the data for the root node of the merged tree.                     *
    *                                                                            *
    *****************************************************************************/
    
    if (bitree_ins_left(merge, NULL, data) != 0) {
    
       bitree_destroy(merge);
       return -1;
    
    }
    
    /*****************************************************************************
    *                                                                            *
    *  Merge the two binary trees into a single binary tree.                     *
    *                                                                            *
    *****************************************************************************/
    
    bitree_root(merge)->left = bitree_root(left);
    bitree_root(merge)->right = bitree_root(right);
    
    /*****************************************************************************
    *                                                                            *
    *  Adjust the size of the new binary tree.                                   *
    *                                                                            *
    *****************************************************************************/
    
    merge->size = merge->size + bitree_size(left) + bitree_size(right);
    
    /*****************************************************************************
    *                                                                            *
    *  Do not let the original trees access the merged nodes.                    *
    *                                                                            *
    *****************************************************************************/
    
    left->root = NULL;
    left->size = 0;
    right->root = NULL;
    right->size = 0;
    
    return 0;
    
    }
    Last edited by thames; 01-15-2013 at 01:50 PM.

  2. #2
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    If I was you, I would transform the trees to lists, then merge the lists and then back to BST's.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  3. #3
    Tears of the stars thames's Avatar
    Join Date
    Oct 2012
    Location
    Rio, Brazil
    Posts
    193
    Quote Originally Posted by std10093 View Post
    If I was you, I would transform the trees to lists, then merge the lists and then back to BST's.
    they are coded as lists I just didn't put all the implementation. Also, this isn't a BST, just a binary tree without the features of the former. Was my line of thought correct?

  4. #4
    SAMARAS std10093's Avatar
    Join Date
    Jan 2011
    Location
    Nice, France
    Posts
    2,675
    binary search tree (BST).

    They seem ok, but you know that I can not really tell, aren't you?
    thames likes this.
    Code - functions and small libraries I use


    It’s 2014 and I still use printf() for debugging.


    "Programs must be written for people to read, and only incidentally for machines to execute. " —Harold Abelson

  5. #5
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,301
    People are commonly very relaxed with their terminology but there are "binary trees" where the nodes may be in any order, and "ordered binary trees" where an in-order traversal of the tree produces the items in sorted order.
    If these are "ordered binary trees" then it is a case of going through one of the trees, possibly in a pre-order traversal, and inserting each node into the other tree, assuming you were to do it destructively.
    However if you want a nicely balanced tree afterwards, the idea of transforming it into a list and then back into a fully balanced tree afterwards produces a good result. Much like the "scapegoat tree"

    If they are not ordered, then how you do it is pretty much up to you, and whatever kind of result you want.
    stahta01 and thames like this.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Binaries
    By egoveneror2 in forum C Programming
    Replies: 2
    Last Post: 04-15-2008, 01:29 AM
  2. Binary Trees MINI MAXING, probability trees
    By curlious in forum General AI Programming
    Replies: 3
    Last Post: 09-30-2005, 10:57 AM
  3. Merging binary search trees
    By ibdutta in forum C Programming
    Replies: 2
    Last Post: 04-16-2004, 07:31 AM
  4. C and C++ binaries
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 01-10-2002, 11:36 AM
  5. traversing binary trees or partial trees
    By sballew in forum C Programming
    Replies: 4
    Last Post: 12-05-2001, 08:19 PM

Tags for this Thread


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21