C++で二分木のノードを葉ノードになった順に出力する方法

問題概要

二分木が与えられたとき、まずその葉ノード（リーフノード）を出力します。次に、出力した葉ノードを木から取り除き、新たに葉ノードとなったノードを出力します。この操作を、木の中にノードが一つも残らなくなるまで繰り返します。

例

以下のような二分木を例に考えてみましょう。

まず最下層の葉ノード「6 7 9 13 14」を出力して取り除き、次に新たな葉ノードとなった「3 4」を出力、続いて「2」、最後に根ノード「1」を出力します。したがって、この問題の出力は以下のようになります。

6 7 9 13 14
3 4
2
1

アプローチ

この問題では、DFS（深さ優先探索）を用いたアプローチを採用します。

具体的には、まずすべてのノードに一時的な値として「0」を割り当てます。その後、DFSで各ノードを訪問しながら、「両方の子ノードの値の最大値 + 1」をそのノードの値として割り当てていきます。

この方法により、葉ノードには「1」、その親ノードには「2」、さらにその上のノードには「3」というように、削除される段階が自動的に記録されます。同じ値を持つノードは同じタイミングで葉ノードとなるため、値ごとにグループ化して出力すれば、求める結果が得られます。

アルゴリズム

開始
ステップ1-> struct Nodeを定義する
    データメンバ: data, order, *left, *right
ステップ2-> struct Node* newNode(int data, int order)を定義する
    struct Node* node = new Node とし、
    node->data = data, node->order = order,
    node->left = NULL, node->right = NULL として node を返す
関数 void postod(struct Node* node, vector<pair<int, int>>& v)
ステップ1-> node == NULL の場合は、
    RETURN（処理を終了）
ステップ2-> 関数 postod(node->left, v) を呼び出す（左の子を先に処理）
ステップ3-> 関数 postod(node->right, v) を呼び出す（次に右の子を処理）
ステップ4-> node->right == NULL かつ node->left == NULL の場合（葉ノード）、
    node->order に 1 を設定
    v.push_back(make_pair(node->order, node->data))
    それ以外の場合、
    node->order = max((node->left)->order, (node->right)->order) + 1
    v.push_back(make_pair(node->order, node->data))
END IF
関数 void printLeafNodes(int n, vector<pair<int, int>>& v)
ステップ1-> sort(v.begin(), v.end()) でベクターをソート
ステップ2-> ループ FOR i = 0 AND i < n AND i++
    v[i].first == v[i + 1].first の場合、
    v[i].second を同じ行に出力
    それ以外の場合、
    v[i].second を改行付きで出力
END FOR
main() 内
ステップ1-> ルートノードを作成: struct Node* root = newNode(1, 0)
ステップ2-> n = 9 を宣言・設定
ステップ3-> postod(root, v) を呼び出す
ステップ4-> printLeafNodes(n, v) を呼び出す
終了

コード例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    int order;
    struct Node* left;
    struct Node* right;
};
struct Node* newNode(int data, int order){
    struct Node* node = new Node;
    node->data = data;
    node->order = order;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
void postod(struct Node* node, vector<pair<int, int> >& v){
    if (node == NULL)
        return;
    /* まず左の子に対して再帰的に処理 */
    postod(node->left, v);
    /* 次に右の子に対して再帰的に処理 */
    postod(node->right, v);
    // 現在のノードが葉ノードの場合、その順序は 1 になる
    if (node->right == NULL && node->left == NULL) {
        node->order = 1;
        // 割り当てた値と木の値のペアを作成
        v.push_back(make_pair(node->order, node->data));
    } else {
        node->order = max((node->left)->order, (node->right)->order) + 1;
        v.push_back(make_pair(node->order, node->data));
    }
}
void printLeafNodes(int n, vector<pair<int, int> >& v){
    sort(v.begin(), v.end());
    for (int i = 0; i < n; i++) {
        if (v[i].first == v[i + 1].first)
            cout << v[i].second << " ";
        else
            cout << v[i].second << "\n";
    }
}
int main(){
    struct Node* root = newNode(1, 0);
    root->left = newNode(2, 0);
    root->right = newNode(3, 0);
    root->left->left = newNode(4, 0);
    root->left->right = newNode(6, 0);
    root->right->left = newNode(14, 0);
    root->right->right = newNode(9, 0);
    root->left->left->left = newNode(7, 0);
    root->left->left->right = newNode(13, 0);
    int n = 9;
    vector<pair<int, int> > v;
    postod(root, v);
    printLeafNodes(n, v);
    return 0;
}

出力

このプログラムを実行すると、以下の出力が得られます。

6 7 9 13 14
3 4
2
1