数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序中一次遍历二叉树的密度
在本教程中，我们将学习如何通过单次遍历来查找二叉树的密度。
二叉树的密度是通过将树的大小除以树的高度得到的。
二叉树的大小是在给定二叉树中存在的节点总数。
二叉树的高度是从根节点到叶节点的最大深度。
让我们看看解决这个问题的步骤。
初始化二叉树的虚拟数据。
查找树的大小和高度。
递归计算树的高度。
如果左子树高度大于右子树高度，则返回左子树高度加1；否则返回右子树高度加1。
递增节点的大小。
使用公式 $$树的大小 / 树的高度$$ 计算树的密度。
打印树的密度。
示例
让我们看看代码。
#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
结论
如果您在本教程中有任何疑问，请在评论区提出。
更新于：2021年1月27日
223 次浏览
广告