C ++の1つのトラバーサルにおける二分木の密度？

二分木の密度は、そのサイズを高さで割って計算されます。二分木の密度=サイズ/高さ。

まず、データとその左右のノードの子を含むツリーノードを表す構造体を定義しましょう。これが最初に作成されるノードの場合はルートノード、それ以外の場合は子ノードです。

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

次に、int値を取得してノードのデータメンバーに割り当てるcreateNode（int data）関数を作成します。この関数は、作成された構造体ノードへのポインターを返します。また、新しく作成されたノードの左右の子はnullに設定されます。

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

treeDensity（Node * root）関数は、ルートノードを取得し、そのnullかどうかを確認します。次に、サイズ変数を宣言して0に設定します。heightAndSize（root、size）関数の戻り値は、height変数に割り当てられます。次に、高さとサイズの間で実行されたフロート除算が返されます。

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

次に、heightAndSize（Node * node、int＆size）は、ルートノードとサイズ変数への参照を取得します。ルートノードがnullの場合、0が返されます。各サブツリーの高さは再帰的に計算され、サイズは再帰ごとに増加します。次に、左または右のサブツリーの大きい方を返します。

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