C++で再帰を使わずに二分木のルートからリーフまでのパスを出力する方法

二分木が与えられたとき、ルートからリーフ（葉）までの複数のパスをすべて出力する必要があります。しかし、ここでの課題は再帰を使用せずに実装することです。

通常、木の探索には再帰がよく使われますが、今回は制約として再帰が使えないため、反復処理（イテレーティブな方法）で木を走査します。そのために、STLのmapを活用します。このマップには各ノードとその親ノードの対応関係を格納し、レベル順走査（またはスタックを用いた走査）によってリーフノードを検出した時点で、親へのポインタをたどることでルートからリーフまでのパスを出力できます。

上記の二分木の場合、ルートからリーフまで到達するためのパスは以下のように複数存在します。

10 -> 3 -> 140
10 -> 3 -> 162
10 -> 211 -> 100
10 -> 211 -> 146

したがって、プログラムは与えられた二分木に対して、これらのパスをすべて出力しなければなりません。

アルゴリズム

START
Step 1 -> ノードの構造体を作成する
   struct Node
      struct node *left, *right
      int data
   End
Step 2 -> 新しいノードを作成する関数
   node* newnode(int data)
   node->data = data
   node->left = node->right = NULL;
   return (node)
Step 3 -> パスを計算する関数を作成する
   void calculatePath(Node* curr, map<Node*, Node*> first)
   STL stack<Node*> stk を作成
   While (curr) の間ループ
      stk.push(curr)
      curr = first[curr]
   End
   !stk.empty() の間ループ
      curr = stk.top()
      stk.pop()
      curr->data を出力
   End
Step 4 -> リーフノードを見つける関数を作成する
   void leaf(Node* root)
   IF root = NULL ならば
      Return
   End
   STL stack<Node*> stc を作成
   stc.push(root)
   STL map<Node*, Node*> prnt を作成
   prnt[root] = NULL
   !stc.empty() の間ループ
      Node* curr = stc.top()
      stc.pop()
      IF !(curr->left) && !(curr->right) ならば
         calculatePath(curr, prnt)
      End
      IF curr->right ならば
         prnt[curr->right] = curr
         stc.push(curr->right)
      End
      IF curr->left ならば
         prnt[curr->left] = curr
         stc.push(curr->left)
      End
   End
STOP

処理の流れのポイント

• スタックによる走査： 再帰の代わりにstackを使ってノードを管理することで、深さ優先的な走査を実現しています。
• 親情報の記録： map<Node*, Node*>に「子ノード → 親ノード」の対応を保存しておくことで、後からリーフからルート方向へ遡れるようにしています。
• パスの出力： リーフノードが見つかったら、マップをたどってルートまで遡りながらスタックに積み、最後にスタックから取り出すことで正しい順序（ルート→リーフ）でパスを出力します。

実装例

#include <bits/stdc++.h>
using namespace std;
// ノードの構造体
struct Node{
   int data;
   struct Node *left, *right;
};
// 新しいノードを作成する関数
Node* newNode(int data){
   Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return node;
}
// パスを計算して出力する関数
void calculatePath(Node* curr, map<Node*, Node*> first){
   stack<Node*> stk;
   while (curr){
      stk.push(curr);
      curr = first[curr];
   }
   while (!stk.empty()){
      curr = stk.top();
      stk.pop();
      cout << curr->data << " ";
   }
   cout << endl;
}
// リーフノードを検出してパスを出力する関数
void leaf(Node* root){
   if (root == NULL)
      return;
   stack<Node*> stc;
   stc.push(root);
   map<Node*, Node*> prnt;
   prnt[root] = NULL;
   while (!stc.empty()){
      Node* curr = stc.top();
      stc.pop();
      if (!(curr->left) && !(curr->right))
         calculatePath(curr, prnt);
      if (curr->right){
         prnt[curr->right] = curr;
         stc.push(curr->right);
      }
      if (curr->left){
         prnt[curr->left] = curr;
         stc.push(curr->left);
      }
   }
}
int main(){
   Node* root = newNode(67); // ツリーを構築するためにノードを挿入
   root->left = newNode(34);
   root->right = newNode(89);
   root->left->left = newNode(23);
   root->left->right = newNode(95);
   root->right->left = newNode(12);
   leaf(root); // leaf関数を呼び出し
   return 0;
}

出力結果

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

67 34 23
67 34 95
67 89 12

このように、再帰を一切使わずにスタックとマップを組み合わせるだけで、二分木のすべてのルートからリーフへのパスを出力できることがわかります。