資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告