document.write('
Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. class Node
  6. {
  7.     public:
  8.         int data;
  9.         Node * left;
  10.         Node * right;
  11. };
  12.  
  13. class BST
  14. {
  15.     Node * root;
  16.     Node * head; // head of list
  17.    
  18.     // Utility functions
  19.    
  20.     Node * newNode (int);
  21.     void insert (Node **, int);
  22.     Node * treeToList (Node *);
  23.     Node * append (Node *, Node *);
  24.     void join (Node *, Node *);
  25.    
  26.     public:
  27.         BST ()
  28.         {
  29.             root = NULL;
  30.         }
  31.        
  32.         // Public functions to be called from main
  33.        
  34.         void insert (int);    
  35.         void toList ();
  36.         void printList ();
  37. };
  38.  
  39. Node * BST :: newNode (int data)
  40. {
  41.     Node * node = new Node;
  42.     node -> data = data;
  43.     node -> left = NULL;
  44.     node -> right = NULL;
  45.     return node;
  46. }
  47.  
  48. void BST :: insert (int data)
  49. {
  50.     insert (&root, data);
  51. }
  52.  
  53. void BST :: insert (Node ** root, int data)
  54. {
  55.     if (!(*root))
  56.         *root = newNode (data);
  57.     else
  58.     {
  59.         if (data <= (*root) -> data)
  60.             insert (&((*root) -> left), data);
  61.         else
  62.             insert (&((*root) -> right), data);
  63.     }
  64. }
  65.  
  66. void BST :: toList ()
  67. {
  68.     head = treeToList (root);
  69. }
  70.  
  71. Node * BST :: treeToList (Node * root)
  72. {
  73.     if (!root)  return NULL;
  74.    
  75.     // Convert the left subtree into circular linked list
  76.     Node * left = treeToList (root -> left);
  77.     // Convert the right subtree into circular linked list
  78.     Node * right = treeToList (root -> right);
  79.    
  80.     // Construct single node linked list out of root
  81.     root -> left = root;
  82.     root -> right = root;
  83.    
  84.     // Append root to the list of left subtree
  85.     left = append (left, root);
  86.     // Append the list of right subtree to the list
  87.     left = append (left, right);
  88.    
  89.     return left;
  90. }
  91.  
  92. Node * BST :: append (Node * a, Node * b)
  93. {
  94.     if (!a) return b;
  95.     if (!b) return a;
  96.    
  97.     // Get last node of first list (to join with second list)
  98.     Node * aLast = a -> left;
  99.     // Get last node of second list (to join with first list)
  100.     Node * bLast = b -> left;
  101.    
  102.     // Join last node of first list to the head of second list
  103.     join (aLast, b);
  104.     // Join last node of second list to the head of first list
  105.     join (bLast, a);
  106.    
  107.     // a is the head of the circular list
  108.     return a;
  109. }
  110.  
  111. void BST :: join (Node * a, Node * b)
  112. {
  113.     // Join last node of a to head of b
  114.     a -> right = b;
  115.     // Join last node of b to head of a
  116.     b -> left = a;
  117. }
  118.  
  119. void BST :: printList ()
  120. {
  121.    
  122.     if (!head) return;
  123.     Node * cur = head;
  124.     while (cur)
  125.     {
  126.         cout << cur -> data << " ";
  127.         cur = cur -> right;
  128.         if (cur == head)
  129.             break;
  130.     }
  131.     cout << endl;
  132. }
  133.  
  134. int main (void)
  135. {
  136.     BST bst;
  137.  
  138.     bst.insert (8);
  139.     bst.insert (3);
  140.     bst.insert (10);
  141.     bst.insert (1);
  142.     bst.insert (6);
  143.     bst.insert (14);
  144.     bst.insert (4);
  145.     bst.insert (7);
  146.     bst.insert (13);
  147.    
  148.     bst.toList ();
  149.     bst.printList ();
  150.    
  151.     return 0;
  152. }
');