C++

Forum

 
program c++ with two function to check if the tree (semtrical +identical)

Sep 22, 2021 at 1:22pm
closed account (Nwb4iNh0)
I just created program with two functions to check if the tree is symmetric or the trees are identical, but yet I can not RUN this program and I dont know where are the errors!
Any help or suggestion 

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;

    
}
Edit & run on cpp.sh
Last edited on Sep 22, 2021 at 1:24pm
Sep 22, 2021 at 2:01pm
coder777 (8447)
Line 3: Missing u
Line 19: Missing ;
Line 48: Remove :
Sep 22, 2021 at 2:23pm
seeplus (6617)
This compiles OK:

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
 
#include <iostream>

struct Node {
	int ID {};
	Node *left {}, *right {};
	Node(int id) : ID(id) {}
};

Node* createTree();

void setAllIDareEqual(Node* Z);
bool areTreesIdentical(const Node* a, const Node* b);
bool isTreeSymmetric(const Node* a, const Node* b);

int main() {
	auto gRoot1 {createTree()};
	auto gRoot2 {createTree()};

	std::cout << "\n\nBoth are  "
		<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";

	delete gRoot2->right->right->left;
	gRoot2->right->right->left = nullptr;

	std::cout << "\n\nBoth are  "
		<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";

	delete gRoot1->right->right->left;
	gRoot1->right->right->left = nullptr;

	std::cout << "\n\nBoth are "
		<< (!areTreesIdentical(gRoot1, gRoot2) ? "NOT " : "") << "identical.";

	std::cout << "\n\nTree is  "
		<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " : "") << "symetric.";

	delete gRoot1->right->right->right;
	gRoot1->right->right->right = nullptr;

	std::cout << "\n\nTree is  "
		<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " : "") << "Symetric.";

	setAllIDareEqual(gRoot1);

	std::cout << "\n\nTree is  "
		<< (!isTreeSymmetric(gRoot1, gRoot1) ? "NOT " : "") << "Symetric.";

	std::cout << "\n\n\n";
}

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(const Node* a, const Node* b) {
	if (a == nullptr && b == nullptr)  return true;

	if (a != nullptr && b != nullptr)
		return (a->ID == b->ID && areTreesIdentical(a->left, b->left) && areTreesIdentical(a->right, b->right));

	return false;
}

bool isTreeSymmetric(const Node* a, const Node* b) {
	if (a == nullptr && b == nullptr) return true;

	if (a && b && a->ID == b->ID)
		return isTreeSymmetric(a->left, b->right) && isTreeSymmetric(a->right, b->left);

	return false;
}
Edit & run on cpp.sh


and displays:


Both are  identical.

Both are  NOT identical.

Both are identical.

Tree is  NOT symetric.

Tree is  NOT Symetric.

Tree is  Symetric.


but whether this is correct..........

Note there is a memory issue as the allocated memory isn't released.
Sep 22, 2021 at 2:27pm
closed account (Nwb4iNh0)
oh thanks for reply
Last edited on Sep 23, 2021 at 1:06pm
Sep 22, 2021 at 4:37pm
seeplus (6617)
Don't you know what the result should be?
Topic archived. No new replies allowed.