CPP 10
Binary-tree.cpp Guest on 5th April 2021 10:48:03 AM
  1. /*
  2.  * binary-tree.cpp
  3.  *
  4.  *  Created on: 8 Sep 2016
  5.  *      Author: lucascordeiro
  6.  */
  7. #include <iostream>
  8. #include <cassert>
  9. using namespace std;
  10.  
  11. template <class T>
  12. class nodet
  13. {
  14. public:
  15.     T key;
  16.     nodet *p;
  17.     nodet *left;
  18.     nodet *right;
  19. };
  20.  
  21. template <class T>
  22. class treet
  23. {
  24. public:
  25.     treet();
  26.     void preorder_tree_walk(nodet<T> *x);
  27.     void inorder_tree_walk(nodet<T> *x);
  28.     void posorder_tree_walk(nodet<T> *x);
  29.     void insert_node(nodet<T> *z, T key);
  30.     nodet<T> *delete_node(nodet<T> *z);
  31.     nodet<T> *tree_search(nodet<T> *x, T k);
  32.     nodet<T> *tree_successor(nodet<T> *x);
  33.     nodet<T> *tree_minimum(nodet<T> *x);
  34.     nodet<T> *tree_maximum(nodet<T> *x);
  35.     nodet<T> *get_root();
  36. private:
  37.     nodet<T> *root;
  38. };
  39.  
  40. template <class T>
  41. treet<T>::treet()
  42. {
  43.     root = NULL;
  44. }
  45.  
  46. template <class T>
  47. void treet<T>::preorder_tree_walk(nodet<T> *x)
  48. {
  49.   if (x!=NULL)
  50.   {
  51.     cout << "node: " << x->key << endl;
  52.     preorder_tree_walk(x->left);
  53.     preorder_tree_walk(x->right);
  54.   }
  55. }
  56.  
  57. template <class T>
  58. void treet<T>::inorder_tree_walk(nodet<T> *x)
  59. {
  60.   if (x!=NULL)
  61.   {
  62.     inorder_tree_walk(x->left);
  63.     cout << "node: " << x->key << endl;
  64.     inorder_tree_walk(x->right);
  65.   }
  66. }
  67.  
  68. template <class T>
  69. void treet<T>::posorder_tree_walk(nodet<T> *x)
  70. {
  71.   if (x!=NULL)
  72.   {
  73.     posorder_tree_walk(x->left);
  74.     posorder_tree_walk(x->right);
  75.     cout << "node: " << x->key << endl;
  76.   }
  77. }
  78.  
  79. template <class T>
  80. void treet<T>::insert_node(nodet<T> *z, T key)
  81. {
  82.   nodet<T> *y, *x;
  83.   z = new nodet<T>;
  84.   z->key=key; z->left=NULL; z->right=NULL; y = NULL; x=root;
  85.   while (x != NULL)
  86.   {
  87.     y = x;
  88.     if (z->key < x->key) x = x->left;
  89.     else x = x->right;
  90.   }
  91.  
  92.   z->p = y;
  93.   if (y==NULL) {root = z; root->left=NULL; root->right=NULL;}
  94.   else if (z->key < y->key) y->left = z;
  95.   else if (z->key > y->key) y->right = z;
  96. }
  97.  
  98. template <class T>
  99. nodet<T> *treet<T>::delete_node(nodet<T> *z)
  100. {
  101.     nodet<T> *y, *x;
  102.     if (z->left==NULL || z->right==NULL)
  103.         y=z; //z has one child only
  104.     else
  105.         y=tree_successor(z); //z has two children
  106.  
  107.     //x is the child not NILL of z
  108.     if (y->left!=NULL)
  109.         x=y->left;
  110.     else
  111.         x=y->right;
  112.  
  113.     if (x!=NULL)
  114.         x->p=y->p;
  115.  
  116.     if (y->p==NULL)
  117.         root=x;
  118.     else if (y==y->p->left)
  119.         y->p->left=x;
  120.     else
  121.         y->p->right=x;
  122.  
  123.     if (y!=z)
  124.     {
  125.         z->key=y->key;
  126.         z->left=y->left;
  127.         z->right=y->right;
  128.         z->p=y->p;
  129.     }
  130.     return y;
  131. }
  132.  
  133. template <class T>
  134. nodet<T> *treet<T>::tree_search(nodet<T> *x, T k)
  135. {
  136.   if (x == NULL || k == x->key)
  137.     return x;
  138.   if (k < x->key)
  139.     tree_search(x->left, k);
  140.   else
  141.     tree_search(x->right,k);
  142. }
  143.  
  144. template <class T>
  145. nodet<T> *treet<T>::tree_successor(nodet<T> *x)
  146. {
  147.     if (x->right!=NULL)
  148.         return tree_minimum(x->right);
  149.     nodet<T> *y;
  150.     y = x->p;
  151.     while (y!=NULL && x==y->right)
  152.     {
  153.         x=y;
  154.         y = x->p;
  155.     }
  156.     return y;
  157. }
  158.  
  159. template <class T>
  160. nodet<T> *treet<T>::tree_minimum(nodet<T> *x)
  161. {
  162.   while (x->left != NULL)
  163.     x=x->left;
  164.   return x;
  165. }
  166.  
  167. template <class T>
  168. nodet<T> *treet<T>::tree_maximum(nodet<T> *x)
  169. {
  170.   while (x->right != NULL)
  171.     x=x->right;
  172.   return x;
  173. }
  174.  
  175. template <class T>
  176. nodet<T> *treet<T>::get_root()
  177. {
  178.     return root;
  179. }
  180.  
  181. int main(void)
  182. {
  183.   nodet<char> *t = new nodet<char>;
  184.   treet<char> *n = new treet<char>;
  185.   n->insert_node(t, 'F');
  186.   n->insert_node(t, 'C');
  187.   n->insert_node(t, 'E');
  188.   n->insert_node(t, 'L');
  189.   n->insert_node(t, 'G');
  190.   n->insert_node(t, 'A');
  191.   n->insert_node(t, 'B');
  192.   n->insert_node(t, 'I');
  193.   n->insert_node(t, 'H');
  194.   n->insert_node(t, 'J');
  195.  
  196.   cout << "### inorder_tree_walk: " << endl;
  197.   n->inorder_tree_walk(n->get_root());
  198.  
  199.   cout << "### preorder_tree_walk: " << endl;
  200.   n->preorder_tree_walk(n->get_root());
  201.  
  202.   cout << "### posorder_tree_walk: " << endl;
  203.   n->posorder_tree_walk(n->get_root());
  204.  
  205.   t = n->tree_search(n->get_root(),'A');
  206.   assert(t->key == 'A');
  207.   cout << "### tree_search: " << 'A' << "==" << t->key << endl;
  208.  
  209.   t = n->tree_minimum(n->get_root());
  210.   assert(t->key == 'A');
  211.   cout << "### tree_minimum: " << t->key << endl;
  212.  
  213.   t = n->tree_maximum(n->get_root());
  214.   assert(t->key == 'L');
  215.   cout << "### tree_maximum: " << t->key << endl;
  216.  
  217.   t = n->tree_search(n->get_root(),'A');
  218.   t = n->tree_successor(t);
  219.   cout << "### tree_successor: " << t->key << endl;
  220.  
  221.   t = n->tree_search(n->get_root(),'B');
  222.   t = n->delete_node(t);
  223.   cout << "### delete_node: " << t->key << endl;
  224.   t = n->tree_search(n->get_root(),'A');
  225.   t = n->tree_successor(t);
  226.   cout << "### tree_successor after deleting 'B': " << t->key << endl;
  227.  
  228.   return 0;
  229. }

Paste-bin is for source code and general debugging text.

Login or Register to edit, delete and keep track of your pastes and more.

Raw Paste

Login or Register to edit or fork this paste. It's free.