（1）2叉樹最大寬度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 題目: 2叉樹的最大寬度
* 來源：經典面試題
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
// 2叉樹的最大寬度
int MaxWidthBinaryTree(TreeNode *root){
if(root == NULL){
return 0;
}//if
// 當前層
queue<TreeNode*> curLevel;
// 下1層
queue<TreeNode*> nextLevel;
// 最大寬度
int max = 0;
// 當前層寬度
int width = 0;
// 加入隊列
curLevel.push(root);
TreeNode *node;
while(!curLevel.empty()){
width = 0;
while(!curLevel.empty()){
++width;
if(width > max){
max = width;
}//if
node = curLevel.front();
curLevel.pop();
// 左子樹
if(node->left != NULL){
nextLevel.push(node->left);
}//if
// 右子樹
if(node->right != NULL){
nextLevel.push(node->right);
}//if
}//while
swap(curLevel,nextLevel);
}//while
return max;
}
//按先序序列創建2叉樹
int CreateBTree(TreeNode*& T){
int data;
//按先序次序輸入2叉樹中結點的值,⑴表示空樹
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//構造左子樹
CreateBTree(T->left);
//構造右子樹
CreateBTree(T->right);
}
return 0;
}
int main() {
TreeNode *root = NULL;
CreateBTree(root);
int result = MaxWidthBinaryTree(root);
cout<<result<<endl;
return 0;
}
（2）2叉樹各層寬度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 題目: 2叉樹的最大寬度
* 來源：經典面試題
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
// 2叉樹寬度
vector<int> WidthBinaryTree(TreeNode *root){
vector<int> level;
if(root == NULL){
return level;
}//if
// 當前層
queue<TreeNode*> curLevel;
// 下1層
queue<TreeNode*> nextLevel;
// 當前層寬度
int width = 0;
// 加入隊列
curLevel.push(root);
TreeNode *node;
while(!curLevel.empty()){
width = 0;
while(!curLevel.empty()){
++width;
node = curLevel.front();
curLevel.pop();
// 左子樹
if(node->left != NULL){
nextLevel.push(node->left);
}//if
// 右子樹
if(node->right != NULL){
nextLevel.push(node->right);
}//if
}//while
level.push_back(width);
swap(curLevel,nextLevel);
}//while
return level;
}
//按先序序列創建2叉樹
int CreateBTree(TreeNode*& T){
int data;
//按先序次序輸入2叉樹中結點的值,⑴表示空樹
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//構造左子樹
CreateBTree(T->left);
//構造右子樹
CreateBTree(T->right);
}
return 0;
}
int main() {
TreeNode *root = NULL;
CreateBTree(root);
vector<int> result = WidthBinaryTree(root);
for(int i = 0;i < result.size();++i){
cout<<"第"<<i+1<<"層->"<<result[i]<<"個節點"<<endl;
}//for
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
