C++で二分木のすべての葉ノードを右から左の順に出力する方法

問題概要

この記事では、二分木(binary tree)が与えられたとき、そのすべての葉ノード(リーフノード)を右から左の順で出力する方法を解説します。

まず、具体例を使って問題を確認しましょう。

入力例

出力例

7 4 1

この問題を解くには、二分木を走査(トラバース)する必要があります。走査のアプローチは主に次の2つがあります。

方法1:前順走査(Preorder Traversal)+ 再帰

前順走査は再帰を用いた手法で、通常は「根 → 左部分木 → 右部分木」の順にノードを訪問します。ただし今回は右から左へ出力する必要があるため、再帰呼び出しの順序を「右部分木 → 左部分木」にするのがポイントです。

葉ノード(左右どちらの子も持たないノード)に到達したらその値を出力し、そうでない場合は子ノードをさらに探索して葉ノードを探します。

実装例

#include <iostream>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
Node* insertNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
void findLeafNode(Node* root) {
    if (!root)
        return;
    if (!root->left && !root->right) {
        cout<<root->data<<"\t";
        return;
    }
    if (root->right)
        findLeafNode(root->right);
    if (root->left)
        findLeafNode(root->left);
}
int main() {
    Node* root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(11);
    root->left->left = insertNode(8);
    root->left->right = insertNode(98);
    root->right->left = insertNode(2);
    root->right->right = insertNode(18);
    cout<<"Leaf nodes of the tree from right to left are:\n";
    findLeafNode(root);
    return 0;
}

実行結果

Leaf nodes of the tree from right to left are −
18 2 98 8

このプログラムでは右部分木を優先的に探索するため、木の最も右側にある葉ノードから順に出力されます。

方法2:後順走査(Postorder Traversal)+ スタック

2つ目の方法は、再帰を使わずにスタックを利用した反復処理で葉ノードを見つける手法です。木を後順(右部分木 → 左部分木 → 根)の要領で走査し、葉ノードを見つけたらその値を出力します。

実装例

#include<bits/stdc++.h>
using namespace std;
struct Node {
    Node* left;
    Node* right;
    int data;
};
Node* insertNode(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}
void findLeafNode(Node* tree) {
    stack<Node*> treeStack;
    while (1) {
        if (tree) {
            treeStack.push(tree);
            tree = tree->right;
        } else {
            if (treeStack.empty())
                break;
            else {
                if (treeStack.top()->left == NULL) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (tree->right == NULL)
                        cout<<tree->data<<"\t";
                }
                while (tree == treeStack.top()->left) {
                    tree = treeStack.top();
                    treeStack.pop();
                    if (treeStack.empty())
                        break;
                }
                if (!treeStack.empty())
                    tree = treeStack.top()->left;
                else
                    tree = NULL;
            }
        }
    }
}
int main(){
    Node* root = insertNode(21);
    root->left = insertNode(5);
    root->right = insertNode(11);
    root->left->left = insertNode(8);
    root->left->right = insertNode(98);
    root->right->left = insertNode(2);
    root->right->right = insertNode(18);
    cout<<"Leaf nodes of the tree from right to left are:\n";
    findLeafNode(root);
    return 0;
}

実行結果

Leaf nodes of the tree from right to left are −
18 2 98 8

まとめ

二分木の葉ノードを右から左へ出力する場合、再帰による前順走査(右優先)を使う方法が最もシンプルで分かりやすいです。一方、スタックを使った反復処理のアプローチは、再帰の深さ制限が問題になるような大きな木を扱う際に有効です。どちらの方法も各ノードを1回ずつ訪問するため、計算量はO(n)で効率的に動作します。