C++で2つの二分探索木の共通ノードを出力する方法

この問題では、2つの二分探索木（BST）が与えられ、両方の木に共通して存在するノードを見つけ出し、その値を出力する必要があります。

二分木とは

二分木とは、すべてのノードが最大2つの子ノードを持つ特殊な木構造です。つまり、各ノードは葉ノードであるか、1つまたは2つの子ノードを持つことになります。さらに二分探索木では、「左の子ノード < 親ノード < 右の子ノード」という大小関係が常に成り立つという性質があります。

例

上の図のように2つの二分木が与えられた場合、両方の木に存在する同じ値のノードをすべて出力することが求められます。

アルゴリズムの考え方

この問題は、補助スタックを使用することで効率的に解くことができます。基本的な発想は以下の通りです。

• 両方の木を中順走査（インオーダー）の要領で同時にたどり、ノードへのポインタをスタックに積んでいきます。
• スタックの先頭にある2つのノードの値を比較し、等しい場合は共通ノードとして出力し、両方のスタックからポップして右部分木へ進みます。
• 片方の値が小さい場合は、小さい側のスタックだけをポップして右部分木へ進みます（値が昇順に並ぶため、これで一致候補を絞り込めます）。

二分探索木の中順走査は昇順にソートされた順序でノードを訪問するため、マージ処理のような要領で2つの走査を並行して進められるのがポイントです。

C++での実装例

#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 *> 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

実行結果から、2つの木に共通するノードは 19 と 72 の2つであることがわかります。

計算量

このアルゴリズムの時間計算量は O(n1 + n2) です（n1、n2 はそれぞれの木のノード数）。また、補助スタックに必要な空間計算量も同様に O(n1 + n2) となります。再帰を使わずスタックで反復的に処理するため、深い木でもスタックオーバーフローの心配が少ないのも利点です。