C++の反復アプローチで二分木の全リーフノードを左から右へ出力する方法

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

問題の理解

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

入力 −

出力 − 1 4 7

上図の二分木では、子を持たないノードである「1」「4」「7」が葉ノードに該当し、左から右の順に出力されます。

解決アプローチ

この問題を反復的なアプローチで解くには、深さ優先探索（DFS）を利用します。木の走査は根ノードから開始し、各ノードに対して以下の手順を実行します。

• そのノードが葉ノード（左右どちらの子も持たないノード）であれば、データを出力します。
• 葉ノードでない場合は、まず左の子部分木、次に右の子部分木の順で走査を続けます。

左側の部分木を先に処理することで、すべての葉ノードが自然に左から右の順序で出力されます。

実装例

以下のコードは、この解法をC++で実装したものです。

#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 printLTRLeafNodes(Node *root){
   if (!root)
      return;
   if (!root->left && !root->right) {
      cout<<root->data<<"\t";
      return;
   }
   if (root->left)
      printLTRLeafNodes(root->left);
   if (root->right)
      printLTRLeafNodes(root->right);
}
int main(){
   Node *root = insertNode(21);
   root->left = insertNode(5);
   root->right = insertNode(36);
   root->left->left = insertNode(2);
   root->right->left = insertNode(13);
   root->right->right = insertNode(4);
   root->right->left->left = insertNode(76);
   root->right->left->right = insertNode(9);
   root->right->right->left = insertNode(17);
   root->right->right->right = insertNode(2);
   cout<<"Leaf Nodes of the tree from left to right are :\n";
   printLTRLeafNodes(root);
   return 0;
}

出力結果

Leaf Nodes of the tree from left to right are −
2 76 9 17 2

このように、DFSによる走査を利用すれば、二分木のすべての葉ノードを簡単に左から右の順序で出力できます。