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

このチュートリアルでは、1回の走査で二分木の密度を見つける方法を学習します。

二分木の密度は、木のサイズを木の高さで割って得られます。

二分木のサイズは、特定の二分木に存在するノードの総数です。

二分木の高さは、ルートノードからのリーフノードの最大の深さです。

問題を解決するための手順を見てみましょう。

• 二分木ダミーデータを初期化します。

• 木のサイズと高さを見つけます。

  • 木の高さを再帰的に数えます。

  • 左側のノードツリーの高さが右側のノードツリーの高さよりも大きい場合は、左側のノードツリーの高さを返します。それ以外の場合は、両方に1を加算して、右側のノードツリーの高さを返します。

  • ノードのサイズを増やします。

• 式$$size\：of \：Tree \：/ \：height \：of \：Tree$$を使用して木の密度を計算します。

• 木の密度を印刷します。

例

コードを見てみましょう。

#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

結論

チュートリアルに質問がある場合は、コメントセクションにそのことを記載してください。