fork download
copy 
  1. /* Merge Binary Search Trees
  2.  * http://stackoverflow.com/a/7732490
  3.  * Author: Jiri, http://stackoverflow.com/users/805681/jiri
  4.  * Created 11-Oct-2011 / Reloaded at ideone.com on 24-Jan-2018
  5.  * Programming language C++
  6.  * References:
  7.  * http://stackoverflow.com/questions/7540546/merging-2-binary-search-trees
  8.  * http://d...content-available-to-author-only...t.com/
  9.  * http://c...content-available-to-author-only...d.edu/109/
  10.  * http://w...content-available-to-author-only...e.com/2010/11/convert-binary-search-tree-bst-to.html
  11.  * http://w...content-available-to-author-only...e.com/2010/11/convert-sorted-list-to-balanced-binary.html
  12.  */
  13.  
  14. #include <stdio.h>
  15.  
  16. struct Node {
  17.     int info;
  18.     Node* left;
  19.     Node* right;
  20. };
  21.  
  22. void insert(Node*& root, int info) {
  23.     if (root == 0) {
  24.         root = new Node();
  25.         root->info = info;
  26.     }
  27.     else if (info < root->info) 
  28.         insert(root->left, info);
  29.     else if (info > root->info) 
  30.         insert(root->right, info);
  31.     else 
  32.         printf("Error: duplicate key %d ignored", info);
  33. }
  34.  
  35. void printSpine(Node* head) {
  36.     for (Node* current = head; current; current = current->right)
  37.         printf("%d ", current->info);
  38.     printf("\n");
  39. }
  40.  
  41. void printTree(Node* node, int level) {
  42.     for (int i = 0; i < level; ++i) printf(" ");
  43.     printf("%d\n", node->info);
  44.     if (node->left) 
  45.         printTree(node->left, level + 1);
  46.     if (node->right) 
  47.         printTree(node->right, level + 1);
  48. }
  49.  
  50. void spine(Node *p, Node *& prev, Node *& head) {   
  51.     if (!p) 
  52.         return;   
  53.     spine(p->left, prev, head);   
  54.     if (prev) 
  55.         prev->right = p;   
  56.     else 
  57.         head = p;  
  58.     prev = p;
  59.     p->left = 0;
  60.     spine(p->right, prev, head); 
  61. } 
  62.  
  63. Node* balance(Node *& list, int start, int end) {
  64.     if (start > end) 
  65.         return NULL;  
  66.     int mid = start + (end - start) / 2;    
  67.     Node *leftChild = balance(list, start, mid-1);   
  68.     Node *parent = list;
  69.     parent->left = leftChild;   
  70.     list = list->right;   
  71.     parent->right = balance(list, mid+1, end);   
  72.     return parent; 
  73. }   
  74.  
  75. Node* balance(Node *head) {
  76.     int size = 0;
  77.     for (Node* n = head; n; n = n->right) ++size;
  78.     return balance(head, 0, size-1); 
  79. } 
  80.  
  81. void advance(Node*& last, Node*& n) {
  82.     last->right = n; 
  83.     last = n;
  84.     n = n->right; 
  85. }
  86.  
  87. Node* mergeSpines(Node* n1, Node* n2) {
  88.     Node head;
  89.     Node* last = &head;
  90.     while (n1 || n2) {
  91.         if (!n1) 
  92.             advance(last, n2);
  93.         else if (!n2) 
  94.             advance(last, n1);
  95.         else if (n1->info < n2->info) 
  96.             advance(last, n1);
  97.         else if (n1->info > n2->info) 
  98.             advance(last, n2);
  99.         else {
  100.             advance(last, n1);
  101.             printf("Duplicate key skipped %d \n", n2->info);
  102.             n2 = n2->right;
  103.         }
  104.     }
  105.     return head.right; 
  106. }
  107.  
  108. Node* merge(Node* n1, Node* n2) {
  109.     Node *prev, *head1, *head2;   
  110.     prev = head1 = 0; 
  111.     spine(n1, prev, head1); 
  112.     prev = head2 = 0;
  113.     spine(n2, prev, head2);
  114.     Node* root = mergeSpines(head1, head2);
  115.     return balance(root);
  116. }
  117.  
  118. int main(int argc, char** argv) {
  119.     Node* root1 = 0;    
  120.     insert(root1, 14);
  121.     insert(root1, 12);
  122.     insert(root1, 1);
  123.     insert(root1, 3);
  124.     insert(root1, 56);
  125.     insert(root1, 6);
  126.     insert(root1, 73);
  127.  
  128.     Node* root2 = 0;    
  129.     insert(root2, 4);
  130.     insert(root2, 22);
  131.     insert(root2, 21);
  132.     insert(root2, 13);
  133.     insert(root2, 5);
  134.     insert(root2, 16);
  135.     insert(root2, 7);
  136.  
  137.     Node* root = merge(root1, root2);
  138.     printTree(root, 0);
  139.     return 0; 
  140. } 
  141.  
Success #stdin #stdout 0s 4580KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
12
 4
  1
   3
  6
   5
   7
 21
  14
   13
   16
  56
   22
   73
https://ideone.com/BcSnkq
language:
C++ (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!