C++の2つの二分探索木の共通ノードを印刷する

この問題では、2つの二分探索木が与えられ、共通のノードを見つける必要があります。

二分木 は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは2つの子ノードを持っています。

例

ここでは、2つのバイナリツリーがあり、両方のツリーで同じであるすべてのノードを出力する必要があります。

この問題の解決策を見つけるために補助スタックを使用するプログラムを作成しましょう。 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