2000元阿里云代金券免费领取，2核4G云服务器仅664元/3年，新老用户都有优惠，立即抢购>>>
阿里云采购季（云主机223元/3年）活动入口：请点击进入>>>，
阿里云学生服务器（9.5元/月）购买入口：请点击进入>>>，
（1）二叉树最大宽度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 题目: 二叉树的最大宽度
* 来源：经典面试题
* 博客：
-----------------------------------------------*/
#include <iostream>
#include <queue>
using namespace std;
struct TreeNode{
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
// 二叉树的最大宽度
int MaxWidthBinaryTree(TreeNode *root){
if(root == NULL){
return 0;
}//if
// 当前层
queue<TreeNode*> curLevel;
// 下一层
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;
}
//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
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）二叉树各层宽度
/*---------------------------------------------
* 日期：2015-03-07
* 作者：SJF0115
* 题目: 二叉树的最大宽度
* 来源：经典面试题
* 博客：
-----------------------------------------------*/
#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){}
};
// 二叉树宽度
vector<int> WidthBinaryTree(TreeNode *root){
vector<int> level;
if(root == NULL){
return level;
}//if
// 当前层
queue<TreeNode*> curLevel;
// 下一层
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;
}
//按先序序列创建二叉树
int CreateBTree(TreeNode*& T){
int data;
//按先序次序输入二叉树中结点的值,-1表示空树
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;
}
