C++で二分木の各ノードのセットビット数を出力する方法

二分木が与えられたとき、本記事で紹介する関数は、各ノードに格納されたキーの値を2進数に変換し、その2進表現に含まれるセットビット(1)の個数を返します。

例

キーとして 10、3、211、140、162、100、146 を持つ二分木を考えてみましょう。各キーの2進表現とセットビット数は以下のようになります。

__builtin_popcount 関数について

ここでは GCC が提供する組み込み関数 __builtin_popcount を利用します。この関数を使うことで、自前でビット演算を実装することなく、簡単にセットビット数を取得できます。

関数のプロトタイプは以下の通りです。

int __builtin_popcount(unsigned int)

この関数は、引数として渡された整数の2進表現における1(セットビット)の個数を返します。

アルゴリズム

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 bits(Node* root)
    IF root = NULL
       return
    print __builtin_popcount(root->data)
    bits(root->left)
    bits(root->right)
step 4 -> main() 内で
    Node* root = newnode(10) を使って木を作成する
    root->left = newnode(3)
    call bits(root)
STOP

C++実装例

#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 bits(Node* root){
   if (root == NULL)
   return;
   // __builtin_popcount で現在のノードのセットビット数をカウント
   cout << "bits in node " << root->data << " = " <<__builtin_popcount(root->data)<< "
";
   bits(root->left);
   bits(root->right);
}
int main(){
   Node* root = newnode(10);
   root->left = newnode(3);
   root->left->left = newnode(140);
   root->left->right = newnode(162);
   root->right = newnode(211);
   root->right->left = newnode(100);
   root->right->right = newnode(146);
   bits(root);
   return 0;
}

出力結果

上記のプログラムを実行すると、以下のような出力が得られます。

bits in node 10 = 2
bits in node 3 = 2
bits in node 140 = 3
bits in node 162 = 3
bits in node 211 = 5
bits in node 100 = 3
bits in node 146 = 3

まとめ

このように、二分木を再帰的に走査しながら __builtin_popcount 関数を呼び出すだけで、各ノードのキーに含まれるセットビット数を効率的に出力できます。ビットカウント処理を自分で実装する必要がないため、コードがシンプルになり、可読性も向上します。