数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++中如何在一趟遍历中计算二叉树的密度？
二叉树的密度是通过将其大小除以其高度来计算的。二叉树密度 = 大小/高度。
让我们首先定义一个结构体，该结构体将表示一个树节点，其中包含数据及其左右子节点。如果这是第一个创建的节点，则它是根节点，否则是子节点。
struct Node {
int data;
struct Node *leftChild, *rightChild;
};接下来，我们创建 `createNode(int data)` 函数，该函数接受一个整数值并将其分配给节点的数据成员。该函数返回指向已创建的 `Node` 结构体的指针。此外，新创建节点的左右子节点都设置为 `null`。
Node* createNode(int data){
Node* node = new Node;
node->data = data;
node->leftChild = node->rightChild = NULL;
return node;
}我们的 `treeDensity(Node *root)` 函数接受根节点并检查其是否为空。然后，它声明 `size` 变量并将其设置为 0。`heightAndSize(root, size)` 函数的返回值被赋值给 `height` 变量。然后返回 `height` 和 `size` 之间的浮点数除法结果。
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)` 接受根节点和 `size` 变量的引用。如果根节点为空，则返回 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;
}示例
让我们看一下以下在一趟遍历中查找二叉树密度的实现：
#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
更新于： 2021年1月16日
119 次查看
广告