資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究用 C++ 編寫程式查詢樹的最大深度或高度
在這個問題中，我們給定一棵二叉樹。我們的任務是編寫一個程式來查詢給定樹的最大深度或高度。
讓我們舉個例子來理解這個問題，
樹的高度為 3。
為了找到樹的最大高度，我們將檢查其左子樹和右子樹的高度，並在兩者中的最大值上加 1。這是一個遞迴過程，它將持續到找到樹的最後一個節點，並逐步新增 1 以找到子樹的高度。
以上示例使用此方法解決。
查詢樹的高度，即 height(3) = max(height(5),height(7)) + 1。
為此，我們將計算值為 5 和 7 的節點的高度。
height(5) = max(height(1),height(9)) + 1 以及
height(7) = 1，它沒有可以形成的子樹。
類似地，height(1) = height(9) = 1
height(5) = max(1,1) +1 = 2
height(3) = max(height(5),height(7)) + 1 = max(2,1) + 1 = 3。
所以高度變為 3。
程式說明解決方案，
示例
#include <iostream>
using namespace std;
class node {
public:
int data;
node* left;
node* right;
};
int height(node* node) {
if (node == NULL)
return 0;
else {
int lDepth = height(node->left);
int rDepth = height(node->right);
if (lDepth > rDepth)
return(lDepth + 1);
else return(rDepth + 1);
}
}
node* insertNode(int data) {
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main() {
node *root = insertNode(4);
root->left = insertNode(5);
root->right = insertNode(0);
root->left->left = insertNode(1);
root->left->right = insertNode(9);
cout<<"The height of the given binary tree is "<<height(root);
return 0;
}輸出
The height of the given binary tree is 3
更新於: 2020年4月20日
644 次檢視
廣告