Viết mã để xác định xem hai cây có giống nhau trong C ++ hay không

Trong bài toán này, chúng ta được đưa ra hai cây. Nhiệm vụ của chúng ta là viết mã để kiểm tra xem hai cây có giống hệt nhau hay không.

Hai cây được cho là giống hệt nhau nếu các phần tử của mảng có cùng giá trị và hướng.

Ví dụ

Vì cả hai cây đều có cùng giá trị và vị trí của các phần tử nên cả hai cây đều giống nhau.

Để kiểm tra xem hai cây có giống hệt nhau hay không, chúng tôi sẽ đi từ nút nút đến từng nút của và kiểm tra sự bằng nhau của chúng theo từng bước và nếu tại bất kỳ điểm nào đến các nút không bằng nhau thì trả về -1, biểu thị cây không giống nhau và nếu toàn bộ cây được duyệt qua hoặc cả hai cây đều trống rỗng trả về 1, cho biết các cây giống hệt nhau.

Chương trình minh họa hoạt động của giải pháp trên,

Ví dụ

#include <iostream>
using namespace std;
class node{
   public:
   int data;
   node* left;
   node* right;
};
node* insertNode(int data){
   node* Node = new node();
   Node->data = data;
   Node->left = NULL;
   Node->right = NULL;
   return(Node);
}
int isIdentricalTrees(node* tree1, node* tree2){
   if (tree1 == NULL &amp;&amp; tree2 == NULL)
      return 1;
   if (tree1 != NULL &amp;&amp; tree2 != NULL){
      return( tree1->data == tree2->data &amp;&amp; isIdentricalTrees(tree1->left,
         tree2->left) &amp;&amp; isIdentricalTrees(tree1->right, tree2->right) );
   }
   return 0;
}
int main(){
   node *root1 = insertNode(4);
   node *root2 = insertNode(4);
   root1->left = insertNode(5);
   root1->right = insertNode(0);
   root1->left->left = insertNode(1);
   root1->left->right = insertNode(9);
   root1->right->left = insertNode(7);
   root2->left = insertNode(5);
   root2->right = insertNode(0);
   root2->left->left = insertNode(1);
   root2->left->right = insertNode(9);
   root2->right->left = insertNode(7);
   cout<<"Both the given trees are ";
   if(isIdentricalTrees(root1, root2))
      cout<<"identical";
   else
      cout<<"identical";
   return 0;
}

Đầu ra

Both the given trees are identical