C ++程序中一次遍历的二叉树的密度

在本教程中，我们将学习如何在单个遍历中查找二叉树的密度。

通过将树的大小除以树的高度来获得二叉树的密度。

二叉树的大小是给定二叉树中存在的节点总数。

二叉树的高度是叶节点距根节点的最大深度。

让我们看看解决问题的步骤。

• 初始化二叉树伪数据。

• 找到树的大小和高度。

• 递归计算树的高度。

• 如果左节点树的高度大于右节点树的高度，则返回左节点树的高度；否则，通过将两者都加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

结论