SHARE
TWEET

Untitled

a guest Apr 25th, 2019 60 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4. template<class T>
  5. class BSTNode
  6. {
  7. public:
  8.     T key;
  9.     BSTNode* right;
  10.     BSTNode* left;
  11. public:
  12.     BSTNode()
  13.     {
  14.         right = NULL;
  15.         left = NULL;
  16.     }
  17.     BSTNode(T DATA, BSTNode* right = 0, BSTNode* left = 0)
  18.     {
  19.         key = DATA;
  20.         this->right = right;
  21.         this->left = left;
  22.     }
  23.     BSTNode*getleft() { return left; }
  24.     BSTNode*getright() { return right; }
  25.     T getkey() { return key; }
  26. };
  27. template<class T>
  28. class BSTFCI
  29. {
  30. public:
  31.     BSTNode<T>* root;
  32. public:
  33.     BSTFCI() { root = NULL; }
  34.     BSTFCI(T data)
  35.     {
  36.         root->key = data;
  37.         root->left = root->right = NULL;
  38.     }
  39.  
  40.     //Recursion Function - Inserting new node to the binary search tree.
  41.     BSTNode<T>* Insert_Node(T DATA, BSTNode<T>* node)
  42.     {
  43.         //InCase there is no node create root node.
  44.         if (node == NULL)
  45.         {
  46.             node = new BSTNode<T>;
  47.             node->key = DATA;
  48.             node->left = node->right = NULL;
  49.         }
  50.  
  51.         //InCase given key > node key -- > Go right subtree.
  52.         else if (DATA > node->key)
  53.             node->right = Insert_Node(DATA, node->right); //Calling it self.
  54.  
  55.         //InCase given key < node key -- > Go left subtree.
  56.         else if (DATA < node->key)
  57.             node->left = Insert_Node(DATA, node->left);
  58.  
  59.         return node;
  60.  
  61.     }
  62.  
  63.     void Insert(T DATA)
  64.     {
  65.         root = Insert_Node(DATA, root);
  66.     }
  67.     //Printing nodes left then root then right.
  68.     void PrintTreeInOrder(BSTNode<T> * node)
  69.     {
  70.         if (node != NULL)
  71.         {
  72.             PrintTreeInOrder(node->left);
  73.             cout << node->key << " ";
  74.             PrintTreeInOrder(node->right);
  75.         }
  76.     }
  77.     void PrintTreeInOrder()
  78.     {
  79.         PrintTreeInOrder(root);
  80.         cout << endl;
  81.     }
  82.  
  83.     template <typename T2>
  84.     friend bool areIdentical(BSTNode<T2> * root1, BSTNode<T2> * root2);
  85.     template <typename T2>
  86.     friend bool isSubtree(BSTNode<T2> *t, BSTNode<T2> *S);
  87.     template <typename T2>
  88.     friend bool isSubTree(BSTFCI<T2>* t1, BSTFCI<T2>* t2);
  89. };
  90.  
  91. template<class T2>
  92. bool areIdentical(BSTNode<T2> * root1, BSTNode<T2> *root2)
  93. {
  94.     if (root1 == NULL && root2 == NULL)
  95.         return true;
  96.  
  97.     if (root1 == NULL || root2 == NULL)
  98.         return false;
  99.  
  100.     return (root1->key == root2->key &&
  101.         areIdentical(root1->left, root2->left) &&
  102.         areIdentical(root1->right, root2->right));
  103. }
  104.  
  105. template<class T2>
  106. bool isSubtree(BSTNode<T2> *t, BSTNode<T2> *S)
  107. {
  108.     if (S == NULL)
  109.         return true;
  110.  
  111.     if (t == NULL)
  112.         return false;
  113.  
  114.     if (areIdentical(t, S))
  115.         return true;
  116.  
  117.     return isSubtree(t->left, S) ||
  118.         isSubtree(t->right, S);
  119. }
  120.  
  121. template<class T2>
  122. bool isSubTree(BSTFCI<T2>* t1, BSTFCI<T2>* t2) {
  123.     return isSubtree(t1->root, t2->root);
  124. }
  125.  
  126. int main()
  127. {
  128.     BSTFCI <int> * test1 = new BSTFCI <int>();
  129.     BSTFCI <int>* test2 = new BSTFCI <int>();
  130.  
  131.     test1->Insert(5);
  132.     test1->Insert(7);
  133.     test1->Insert(3);
  134.     test1->Insert(2);
  135.     test1->Insert(9);
  136.     test1->PrintTreeInOrder();
  137.  
  138.     test2->Insert(5);
  139.     test2->Insert(7);
  140.     test2->Insert(3);
  141.     test2->Insert(2);
  142.     test2->Insert(9);
  143.     test2->PrintTreeInOrder();
  144.  
  145.     cout << isSubtree(test1->root, test2->root);
  146.     cout << isSubTree(test1, test2);
  147.  
  148.     return 0;
  149. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top