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

二叉树的密度是通过将其大小除以其height.Binary树密度 = 大小/高度来计算的。

让我们首先定义表示包含数据及其左右节点子节点的树节点的结构。如果这是要创建的第一个节点，则它是根节点，否则是子节点。

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

接下来我们创建我们的createNode(int data)函数，它接受一个 int 值并将其分配给节点的数据成员。该函数返回指向创建的结构节点的指针。此外，新创建的节点的左右子节点设置为空。

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)函数的返回值被分配给高度变量。然后返回在高度和大小之间执行的浮点除法。

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<< "上面给定的二叉树的密度是 "<<treeDensity(root);
   return 0;
}

上面的代码将产生以下输出 -

上面给定的二叉树的密度是 1.5