1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111
|
#include <iostream>
sing namespace std;
struct Node {
int ID;
Node *left, *right;
Node(int id) { ID = id; left = right = nullptr; }
};
Node* gRoot1 = nullptr, *gRoot2 = nullptr;
Node* createTree();
void setAllIDareEqual(Node* Z);
bool areTreesIdentical(Node *a, Node *b);
bool isTreeSymmetric(Node* a, Node* b)
int main() {
gRoot1 = createTree(); gRoot2 = createTree();
cout << "\n\nBoth are "
<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";
delete gRoot2->right->right->left;
gRoot2->right->right->left = nullptr;
cout << "\n\nBoth are "
<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";
delete gRoot1->right->right->left;
gRoot1->right->right->left = nullptr;
cout << "\n\nBoth are "
<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";
cout << "\n\nTree is "
<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " :"") << "symetric.";
:
delete gRoot1->right->right->right; gRoot1->right->right->right = nullptr;
cout << "\n\nTree is "
<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " :"") << "Symetric.";
setAllIDareEqual (gRoot1);
cout << "\n\nTree is "
<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " :"") << "Symetric.";
cout << "\n\n\n";
return 0;
}
Node* createTree() {
Node* p[12];
for (int i = 1; i <= 11; i++) p[i] = new Node(i);
p[1]->left = p[2]; p[1]->right = p[3];
p[2]->left = p[4]; p[2]->right = p[5];
p[3]->left = p[6]; p[3]->right = p[7];
p[5]->left = p[8];
p[6]->right = p[9];
p[7]->left = p[10]; p[7]->right = p[11];
return p[1];
}
void setAllIDareEqual (Node* Z) {
if (Z) {
Z->ID = 99;
setAllIDareEqual (Z->left);
setAllIDareEqual (Z->right);
}
}
bool areTreesIdentical(Node* a, Node* b) {
if(a == NULL && b == NULL) return 1;
if(a != NULL && b != NULL)
return (a -> ID == b -> ID && areTreesIdentical (a -> left, b -> left) && areTreesIdentical(a -> right, b -> right));
return 0;
}
bool isTreeSymmetric(Node* a, Node* b) {
if (a == NULL && b== NULL) return true;
if (a && b && a->ID == b-> ID)
return isTreeSymmetric(a->left, b->right) && isTreeSymmetric(a->right, b->left);
return false;
}
|