資料結構
網路
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 次檢視
廣告