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

二分木の密度とは、木のサイズ（ノードの総数）を高さで割った値として定義されます。

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

ノード構造体の定義

まず、データおよび左右の子ノードへのポインタを保持する、木のノードを表す構造体を定義します。最初に作成されるノードがルートノードとなり、それ以降に作成されるノードは子ノードとして扱われます。

struct Node {
    int data;
    struct Node *leftChild, *rightChild;
};

ノード生成関数（createNode）

次に、createNode(int data) 関数を作成します。この関数はint型の値を受け取り、ノードのdataメンバに代入します。戻り値としては生成されたNode構造体へのポインタを返し、新しく作成されたノードの左右の子にはNULLが設定されます。

Node* createNode(int data){
    Node* node = new Node;
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}

密度を計算する関数（treeDensity）

treeDensity(Node *root) 関数はルートノードを受け取り、それがNULLかどうかを判定します。NULLでない場合は、size変数を宣言して0で初期化します。続いて heightAndSize(root, size) 関数の戻り値をheight変数に代入し、sizeをheightでfloat型として除算した結果を返します。

float treeDensity(Node* root){
    if (root == NULL)
        return 0;
    int size = 0;
    int height = heightAndSize(root, size);
    return (float)size/height;
}

高さとサイズを同時に求める関数（heightAndSize）

heightAndSize(Node* node, int &size) 関数は、ルートノードとsize変数への参照を受け取ります。ノードがNULLの場合は0を返します。各部分木の高さは再帰的に計算され、再帰呼び出しが行われるたびにsizeがインクリメントされます。最後に、左部分木と右部分木の高さを比較し、大きい方に1を加えた値を返します。

int heightAndSize(Node* node, int &size){
    if (node==NULL)
        return 0;
    int left = heightAndSize(node->leftChild, size);
    int right = heightAndSize(node->rightChild, size);
    size++;
    return (left > right) ? ++left : ++right;
}

実装例

以下は、1回の走査で二分木の密度を求めるプログラムの完全な実装例です。

#include<iostream>
using namespace std;
struct Node{
    int data;
    Node *leftChild, *rightChild;
};
Node* createNode(int data){
    Node* node = new Node;
    node->data = data;
    node->leftChild = node->rightChild = NULL;
    return node;
}
int heightAndSize(Node* node, int &size){
    if (node==NULL)
        return 0;
    int left = heightAndSize(node->leftChild, size);
    int right = heightAndSize(node->rightChild, size);
    size++;
    return (left > right) ? ++left : ++right;
}
float treeDensity(Node* root){
    if (root == NULL)
        return 0;
    int size = 0;
    int height = heightAndSize(root, size);
    return (float)size/height;
}
int main(){
    Node* root = createNode(7);
    root->leftChild = createNode(9);
    root->rightChild = createNode(11);
    cout<< "The density of the above given binary tree is "<<treeDensity(root);
    return 0;
}

出力

上記のコードを実行すると、以下の出力が得られます。

The density of the above given binary tree is 1.5

結果の解説

この例では、ルート7に子ノード9と11が接続された3ノードの二分木を扱っています。サイズ（ノード数）は3、高さは2であるため、密度は 3 ÷ 2 ＝ 1.5 となります。このように、高さとサイズを1回の走査で同時に取得することで、計算量をO(n)に抑えながら効率的に密度を求めることができます。