• API
• FAQ
• Tools
• Archive
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.

Top