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

2023-06-21 12:16:03 188

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

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

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

接下来我们创建我们的createNode(intdata)函数，它接受一个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
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<< "上面给定的二叉树的密度是 "<输出结果
上面的代码将产生以下输出-
上面给定的二叉树的密度是 1.5

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

示例

热门推荐

随机推荐