C++의 두 이진 검색 트리에서 공통 노드 인쇄

이 문제에서는 두 개의 이진 탐색 트리가 주어지고 공통 노드를 찾아야 합니다.

이진 트리 모든 노드에 최대 2개의 자식 노드가 있는 특수 트리입니다. 따라서 모든 노드는 리프 노드이거나 하나 또는 두 개의 하위 노드가 있습니다.

예

여기에 두 개의 이진 트리가 있고 두 트리에 대해 동일한 모든 노드를 인쇄해야 합니다.

이 문제에 대한 해결책을 찾기 위해 보조 스택을 사용하는 프로그램을 만들어 봅시다. 두 개의 동일한 값이 발생할 때 요소를 팝업하여 작동합니다.

예시

#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;
}

출력

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