C++で二分木の奇数レベルにあるノードを出力する方法

はじめに

二分木が与えられたとき、プログラムは木の奇数レベルにあるノードを出力する必要があります。ここでいうレベルとは、二分木の階層を表し、ルートをレベル1として1からnまで数えます。

実装方法については特に指定がないため、再帰または反復のどちらかのアプローチを選択できます。本記事では、コードが簡潔になる再帰的なアプローチを採用します。プログラムは関数を再帰的に呼び出し、その関数が奇数レベルのノードを取得して出力します。

上記の二分木の場合 −

レベル1のノード: 10
レベル2のノード: 3 と 211
レベル3のノード: 140、162、100、146

この木では、レベル1とレベル3が奇数レベルに該当します。したがって、出力結果は「10、140、162、100、146」となります。

アルゴリズム

開始
ステップ1 -> ノードの構造体を作成する
    struct Node
        struct node *left, *right
        int data
    End
ステップ2 -> 新しいノードを作成する関数
    node* newnode(int data)
    node->data = data
    node->left = node->right = NULL;
    return (node)
ステップ3 -> 奇数レベルのノードを見つける関数を作成する
    void odd(Node *root, bool ifodd = true)
    IF root = NULL
        Return
    End
    if (ifodd)
        print root->data
    End
    odd(root->left, !ifodd)
    odd(root->right, !ifodd)
ステップ4 -> main() 内で
    Node* root = newnode(45) を使って木を作成する
    root->left = newnode(23)
    odd(root) を呼び出す
終了

仕組みのポイント

このアルゴリズムの鍵となるのは、bool型のフラグ ifodd です。ルートはレベル1(奇数)に位置するため、初期値を true とします。そして、子ノードへ再帰的に降りるたびに !ifodd でフラグを反転させることで、現在のレベルが奇数か偶数かを自動的に判定できます。フラグが true のときだけノードの値を出力することで、奇数レベルのノードだけが表示される仕組みです。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    Node* left, *right;
};
// 奇数レベルのノードを出力する関数
void odd(Node *root, bool ifodd = true){
    if (root == NULL)
        return;
    if (ifodd)
        cout << root->data << " " ;
    odd(root->left, !ifodd);
    odd(root->right, !ifodd);
}
// 新しいノードを作成する関数
Node* newnode(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return (node);
}
int main(){
    Node* root = newnode(45);
    root->left = newnode(23);
    root->right = newnode(13);
    root->left->left = newnode(24);
    root->left->right = newnode(85);
    cout<<"\nodd nodes are ";
    odd(root);
    return 0;
}

出力結果

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

odd nodes are 45 24 85

この結果から、レベル1の「45」、レベル3の「24」と「85」が出力され、レベル2の「23」と「13」は正しくスキップされていることが確認できます。