C++で1回の走査により二分木の密度を求める方法

はじめに

このチュートリアルでは、1回の走査（トラバーサル）だけで二分木の密度を求める方法について解説します。

二分木の密度は、次の式で定義されます。

密度 ＝ 木のサイズ ÷ 木の高さ

• 木のサイズ：与えられた二分木に含まれるノードの総数
• 木の高さ：根ノードから最も深い葉ノードまでの最大深度

アルゴリズムの手順

問題を解くための手順は以下の通りです。

1. 二分木のテストデータを初期化します。
2. 木のサイズと高さを同時に求めます。
   • 再帰的に木の高さを計算します。
   • 左右の部分木の高さを比較し、大きい方に1を加えた値を返します。
   • 訪問したノードごとにサイズをインクリメントします。
3. 「木のサイズ ÷ 木の高さ」という式で密度を計算します。
4. 計算結果である密度を出力します。

実装例

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
int findHeightAndSizeOfTree(Node* node, int &size) {
    if (node == NULL) {
        return 0;
    }
    int leftTreeCount = findHeightAndSizeOfTree(node->left, size);
    int rightTreeCount = findHeightAndSizeOfTree(node->right, size);
    size++;
    return (leftTreeCount > rightTreeCount) ? leftTreeCount + 1 : rightTreeCount + 1;
}
float treeDensity(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int treeSize = 0;
    int treeHeight = findHeightAndSizeOfTree(root, treeSize);
    return (float)treeSize/treeHeight;
}
int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    cout << treeDensity(root) << endl;
    return 0;
}

実行結果

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

2.33333

このサンプルツリーはノードが7個、高さが3であるため、密度は 7 ÷ 3 ≒ 2.33333 となります。

まとめ

このチュートリアルでは、1回の走査で二分木のサイズと高さを同時に取得し、その密度を計算する方法を学びました。各ノードを一度だけ訪問するため、時間計算量はO(n)と非常に効率的です。チュートリアルの内容について質問がある場合は、コメント欄でお気軽にお知らせください。