資料結構
網路技術
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究C++ 中二叉樹的最大寬度
問題陳述
給定一個二叉樹，編寫一個函式，以獲取給定樹的最大寬度。樹的寬度是所有層級中最寬的一個。
考慮以下樹−
10 / \ 7 4 / \ \ 9 2 1 / \ 2 5 1. Width at level 1: 1 2. Width at level 2: 2 3. Width at level 3: 3 4. Width at level 4: 2 For above tree answer is 3.
演算法
1. Use level order traversal to find the answer
示例
#include <bits/stdc++.h>
using namespace std;
struct node {
public:
int data;
node* left;
node* right;
};
int getWidth(node* root, int level);
int height(node* node);
node* newNode(int data);
int getMaxWidth(node* root){
int maxWidth = 0;
int width;
int h = height(root);
int i;
for (i = 1; i <= h; ++i) {
width = getWidth(root, i);
if (width > maxWidth) {
maxWidth = width;
}
}
return maxWidth;
}
int getWidth(node* root, int level){
if (root == NULL) {
return 0;
}
if (level == 1) {
return 1;
}
else if (level > 1) {
return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);
}
}
int height(node* node){
if (node == NULL) {
return 0;
}
int lHeight = height(node->left);
int rHeight = height(node->right);
return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1);
}
node* newNode(int data){
node* Node = new node();
Node->data = data;
Node->left = NULL;
Node->right = NULL;
return(Node);
}
int main(){
node *root = newNode(10);
root->left = newNode(7);
root->right = newNode(4);
root->left->left = newNode(9);
root->left->right = newNode(2);
root->right->right = newNode(1);
root->right->right->left = newNode(2);
root->right->right->right = newNode(5);
cout<<"Maximum width = " << getMaxWidth(root) << endl;
return 0;
}輸出
編譯並執行上述程式時。它將生成以下輸出 −
Maximum width = 3
更新日期: 10-2-2020
238 次瀏覽
廣告