（1）2叉樹(shù)最大寬度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 題目: 2叉樹(shù)的最大寬度
* 來(lái)源：經(jīng)典面試題
* 博客：
-----------------------------------------------*/
#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叉樹(shù)的最大寬度
int MaxWidthBinaryTree(TreeNode *root){
if(root == NULL){
return 0;
}//if
// 當(dāng)前層
queue<TreeNode*> curLevel;
// 下1層
queue<TreeNode*> nextLevel;
// 最大寬度
int max = 0;
// 當(dāng)前層寬度
int width = 0;
// 加入隊(duì)列
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();
// 左子樹(shù)
if(node->left != NULL){
nextLevel.push(node->left);
}//if
// 右子樹(shù)
if(node->right != NULL){
nextLevel.push(node->right);
}//if
}//while
swap(curLevel,nextLevel);
}//while
return max;
}
//按先序序列創(chuàng)建2叉樹(shù)
int CreateBTree(TreeNode*& T){
int data;
//按先序次序輸入2叉樹(shù)中結(jié)點(diǎn)的值,⑴表示空樹(shù)
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//構(gòu)造左子樹(shù)
CreateBTree(T->left);
//構(gòu)造右子樹(shù)
CreateBTree(T->right);
}
return 0;
}
int main() {
TreeNode *root = NULL;
CreateBTree(root);
int result = MaxWidthBinaryTree(root);
cout<<result<<endl;
return 0;
}
（2）2叉樹(shù)各層寬度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 題目: 2叉樹(shù)的最大寬度
* 來(lái)源：經(jīng)典面試題
* 博客：
-----------------------------------------------*/
#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叉樹(shù)寬度
vector<int> WidthBinaryTree(TreeNode *root){
vector<int> level;
if(root == NULL){
return level;
}//if
// 當(dāng)前層
queue<TreeNode*> curLevel;
// 下1層
queue<TreeNode*> nextLevel;
// 當(dāng)前層寬度
int width = 0;
// 加入隊(duì)列
curLevel.push(root);
TreeNode *node;
while(!curLevel.empty()){
width = 0;
while(!curLevel.empty()){
++width;
node = curLevel.front();
curLevel.pop();
// 左子樹(shù)
if(node->left != NULL){
nextLevel.push(node->left);
}//if
// 右子樹(shù)
if(node->right != NULL){
nextLevel.push(node->right);
}//if
}//while
level.push_back(width);
swap(curLevel,nextLevel);
}//while
return level;
}
//按先序序列創(chuàng)建2叉樹(shù)
int CreateBTree(TreeNode*& T){
int data;
//按先序次序輸入2叉樹(shù)中結(jié)點(diǎn)的值,⑴表示空樹(shù)
cin>>data;
if(data == -1){
T = NULL;
}
else{
T = new TreeNode(data);
//構(gòu)造左子樹(shù)
CreateBTree(T->left);
//構(gòu)造右子樹(shù)
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]<<"個(gè)節(jié)點(diǎn)"<<endl;
}//for
return 0;
}
程序員人生，我編程，我富裕，記住wfuyu網(wǎng)，php教程，php學(xué)習(xí)，php手冊(cè)，CMS模版制作
聲明：本站大部分內(nèi)容是作者原創(chuàng)，少部分收集于互聯(lián)網(wǎng)供大家一起學(xué)習(xí)，原版權(quán)很多不明，如有侵權(quán)請(qǐng)聯(lián)系本站，謝謝！
粵ICP備14040726號(hào)-1?? 2015-2020 程序員人生 版權(quán)所有
