Trong bài toán này, chúng ta được cung cấp hai cây tìm kiếm nhị phân và chúng ta phải tìm các nút chung.
Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút con. Vì vậy, mọi nút đều là nút lá hoặc có một hoặc hai nút con.
Ví dụ,
Ở đây, chúng ta có hai cây nhị phân và chúng ta phải in tất cả các nút giống nhau cho cả hai cây.
Hãy tạo một chương trình sử dụng ngăn xếp phụ trợ để tìm giải pháp cho vấn đề này. Nó hoạt động bằng cách xuất hiện các phần tử khi hai giá trị giống nhau phát sinh.
Ví dụ
#include<iostream>
#include<stack>
using namespace std;
struct Node{
int key;
struct Node *left, *right;
};
Node *newNode(int ele){
Node *temp = new Node;
temp->key = ele;
temp->left = temp->right = NULL;
return temp;
}
void printCommon(Node *tree1, Node *tree2){
stack<Node *> stack1, s1, s2;
while (1){
if (tree1){
s1.push(tree1);
tree1 = tree1->left;
}
else if (tree2){
s2.push(tree2);
tree2 = tree2->left;
}
else if (!s1.empty() && !s2.empty()){
tree1 = s1.top();
tree2 = s2.top();
if (tree1->key == tree2->key){
cout << tree1->key << " ";
s1.pop();
s2.pop();
tree1 = tree1->right;
tree2 = tree2->right;
}
else if (tree1->key < tree2->key){
s1.pop();
tree1 = tree1->right;
tree2 = NULL;
}
else if (tree1->key > tree2->key){
s2.pop();
tree2 = tree2->right;
tree1 = NULL;
}
}
else break;
}
}
void inorderTraversal(struct Node *root){
if (root){
inorderTraversal(root->left);
cout<<root->key<<" ";
inorderTraversal(root->right);
}
}
struct Node* insertNode(struct Node* node, int key){
if (node == NULL) return newNode(key);
if (key < node->key)
node->left = insertNode(node->left, key);
else if (key > node->key)
node->right = insertNode(node->right, key);
return node;
}
int main(){
Node *tree1 = NULL;
tree1=insertNode(tree1, 45);
tree1=insertNode(tree1, 87);
tree1=insertNode(tree1, 12);
tree1=insertNode(tree1, 54);
tree1=insertNode(tree1, 89);
tree1=insertNode(tree1, 19);
tree1=insertNode(tree1, 72);
cout<<"Binary Tree 1 : ";
inorderTraversal(tree1);
cout<<endl;
Node *tree2=NULL;
tree2=insertNode(tree2, 72);
tree2=insertNode(tree2, 23);
tree2=insertNode(tree2, 13);
tree2=insertNode(tree2, 1);
tree2=insertNode(tree2, 19);
cout<<"Binary Tree 2 : ";
inorderTraversal(tree2);
cout<<endl;
cout<<"Common Nodes between the two trees : ";
printCommon(tree1, tree2);
return 0;
} Đầu ra
Binary Tree 1 : 12 19 45 54 72 87 89 Binary Tree 2 : 1 13 19 23 72 Common Nodes between the two trees : 19 72