C++で二分木の奇数レベルにあるノードを出力するプログラム

このチュートリアルでは、与えられた二分木（バイナリツリー）の中から、奇数レベルに存在するノードを出力するC++プログラムについて解説します。

本プログラムでは、ルートノードのレベルを「1」と定義し、それ以降のレベルは交互にカウントしていきます。つまり、レベル1・3・5…といった奇数番目の階層に属するノードが出力の対象となります。

例として、以下のような二分木が与えられた場合を考えてみましょう。

この二分木の場合、奇数レベルに存在するノードは 1, 4, 5, 6 となります。

アルゴリズムの考え方

実装には再帰呼び出しを利用します。ルートから探索を開始し、現在のレベルが奇数かどうかをブール値（真偽値）のフラグで管理します。子ノードへ移動するたびにフラグを反転させることで、各ノードが奇数レベルに属しているかどうかを簡単に判定できます。フラグが「true」のときだけ、そのノードの値を出力します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node* left, *right;
};
// 奇数レベルのノードを出力する
void print_onodes(Node *root, bool is_odd = true){
   if (root == NULL)
      return;
   if (is_odd)
      cout << root->data << " " ;
   print_onodes(root->left, !is_odd);
   print_onodes(root->right, !is_odd);
}
// 新しいノードを作成する
struct Node* create_node(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int main(){
   struct Node* root = create_node(13);
   root->left = create_node(21);
   root->right = create_node(43);
   root->left->left = create_node(64);
   root->left->right = create_node(85);
   print_onodes(root);
   return 0;
}

出力

13 64 85

上記のコードでは、ルート（13）がレベル1、その子ノード（21, 43）がレベル2、さらにその下のノード（64, 85）がレベル3に位置します。したがって、奇数レベルであるレベル1とレベル3のノード「13 64 85」が出力されます。