Created
July 18, 2014 18:04
-
-
Save ivycheung1208/1575900cb5e3e74211bc to your computer and use it in GitHub Desktop.
CC150 4.8
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/* CC150 4.8 | |
* You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. | |
* Create an algorithm to decide if T2 is a subtree of Tl. | |
* A tree T2 is a subtree of Tl if there exists a node n in Tl such that the subtree of n is identical to T2. | |
* That is, if you cut off the tree at node n, the two trees would be identical. | |
*/ | |
#include "bstree.h" // https://gist.github.com/df2d3552fbe8c2342541 | |
#include <sstream> | |
using namespace std; | |
bool treeMatch(Node *t1, Node *t2) | |
{ | |
if (t1 == nullptr && t2 == nullptr) // both trees are empty | |
return true; | |
if (t1 == nullptr || t2 == nullptr) // one of the two trees is empty | |
return false; | |
return t1->data == t2->data // both trees are non-empty, first compare current node then compare subtrees | |
&& treeMatch(t1->left, t2->left) && treeMatch(t1->right, t2->right); | |
} | |
bool isSubtree(Node *t1, Node *t2) | |
{ | |
if (t2 == nullptr) // tree t2 is empty | |
return true; | |
if (t1 == nullptr) // tree t1 is empty while t2 is not | |
return false; | |
if (t1->data == t2->data) { // both trees are non-empty | |
if (treeMatch(t1, t2)) | |
return true; // find exact match | |
} | |
return isSubtree(t1->left, t2) || isSubtree(t1->right, t2); // traverse t1 and keep searching for t2 | |
} | |
int main() | |
{ | |
bstree t1; // tree t1 | |
string key1; getline(cin, key1); // data for tree t1 | |
istringstream din(key1); | |
int key; | |
while (din >> key) | |
t1.insert(key); | |
bstree t2; // tree t2 | |
string key2; getline(cin, key2); // data for tree t2 | |
din.clear(); din.str(key2); | |
while (din >> key) | |
t2.insert(key); | |
if (isSubtree(t1.getRoot(), t2.getRoot())) | |
cout << "T2 is subtree of T1!" << endl; | |
else | |
cout << "T2 is not subtree of T1!" << endl; | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment