C++プログラムで二分木の左端・右端ノードを出力する方法

左の子と右の子を持つ二分木が与えられたとき、その木の最も左端および右端に位置するノード(コーナーノード)を出力するのが課題です。

ここでいう「左端ノード」とは、各レベルにおいて親ノードから見て左側に連なるノードのことを指し、「右端ノード」とは、ルートから見て右側に連なるノードのことを指します。

この問題は、キューを用いたレベル順走査(幅優先探索:BFS)で効率的に解くことができます。各レベルの最初のノードと最後のノードだけを結果に追加していけば、木全体の左右の端の値が得られます。

例

入力: 106 20 320 100 21 61 52
出力: 106 20 320 100 52

この例では、各レベルの左端と右端のノード(106 / 20・320 / 100・52)が出力されています。

アルゴリズム

開始
ステップ1 → ノードの構造体を作成する
    int data を宣言
    struct node *left と *right を宣言
ステップ2 → struct node* newNode(int val) を作成する
    node* temp = new node を生成
    temp->data = val を設定
    temp->left = temp->right = NULL を設定
    return (temp)
ステップ3 → 関数 void print(node *root) を宣言する
    IF root == NULL ならば
        Return
    STL の queue<node*> que を用意
    que.push(root) を呼び出す
    STL の vector<int> ans を用意
    Loop While !que.empty()
        int n = que.size() を設定
        Loop for int i = 0、i < n、i++
            node *temp = que.front()
            que.pop()
            IF i == 0 ならば
                ans.push_back(temp->data)
            ELSE IF i == n-1 ならば
                ans.push_back(temp->data)
            IF temp->left が存在すれば
                que.push(temp->left)
            IF temp->right が存在すれば
                que.push(temp->right)
        End
    Loop For auto i : ans
        i を出力
    End
ステップ4 → main() 内で
    node *root = newNode(106) でノードを作成
    print(root) を呼び出す
終了

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体 {
    int data;
    struct node* left, *right;
};
// 新しいノードを作成する関数
struct node* newNode(int val){
    node* temp = new node;
    temp->data = val;
    temp->left = temp->right = NULL;
    return (temp);
}
// 木のコーナー要素(左右の端)を出力する関数
void print(node *root) {
    if(root == NULL)
    return;
    queue<node*> que;
    que.push(root);
    vector<int> ans;
    while(!que.empty()){
        int n = que.size();
        for(int i =0;i<n;i++){
            node *temp = que.front();
            que.pop();
            if(i==0)
                ans.push_back(temp->data);
            else if(i==n-1)
                ans.push_back(temp->data);
            if(temp->left)
                que.push(temp->left);
            if(temp->right)
                que.push(temp->right);
        }
    }
    for(auto i : ans)
        cout << i << " ";
}
int main (){
    node *root = newNode(106);
    root->left = newNode(20);
    root->right = newNode(320);
    root->left->left = newNode(100);
    root->left->right = newNode(21);
    root->right->left = newNode(61);
    root->right->right = newNode(52);
    print(root);
    return 0;
}

出力

上記のプログラムを実行すると、次のような出力が得られます。

106 20 320 100 52

このアルゴリズムの計算量は、全ノードを一度ずつ訪問するため O(n)(n はノード数)、必要な記憶領域はキューのサイズに依存し、最悪ケースで O(n) となります。