(1)二叉树最大宽度
#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;
}
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;
}
node = curLevel.front();
curLevel.pop();
if(node->left != NULL){
nextLevel.push(node->left);
}
if(node->right != NULL){
nextLevel.push(node->right);
}
}
swap(curLevel,nextLevel);
}
return max;
}
int CreateBTree(TreeNode*& T){
int data;
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)二叉树各层宽度
#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;
}
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(node->right != NULL){
nextLevel.push(node->right);
}
}
level.push_back(width);
swap(curLevel,nextLevel);
}
return level;
}
int CreateBTree(TreeNode*& T){
int data;
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;
}
return 0;
}
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
求二叉树最大宽度 数据结构 求二叉树最大宽度 数据结构
java基础面试题二叉树的深度本资源系百度网盘分享地址
java基础面试题二叉树的镜像本资源系百度网盘分享地址
二叉树面试题 树和二叉树考研试题总结
java基础面试题二叉树的下一个节点本资源系百度网盘分享地址
java基础面试题二叉树中和为某一值的路径本资源系百度网盘分享地址
IT面试题-二叉树的三种遍历的递归与非递归实现,详细代码,包含了前先序遍历,中序遍历、后序遍历的递归实现和非递归实现,文档内有详细的实现代码。
java基础面试题平衡二叉树本资源系百度网盘分享链接
解决二叉树初始化,宽度,高度,最大节点,是否为完全二叉树的判断
剑指offer面试题(7)——重建二叉树整体工程代码,C++语言实现。
二叉树模板代码 二叉树 作业习题 二叉树模板代码 二叉树 作业习题 二叉树模板代码 二叉树 作业习题
这个demo里面主要介绍了有关二叉树的算法面试题,希望可以帮助需要的同学.
java基础面试题把二叉树打印成多行
武汉理工大学数据结构课程设计计算二叉树的宽度
二叉树的建立,前序、中序、后序、层序遍历,求二叉树的宽度
主要介绍了C语言中计算二叉树的宽度的两种方式的相关资料,需要的朋友可以参考下
C语言用递归法将二叉树层序遍历,并求出最大宽度。文件类型是.cpp的,c的编译器都可以编译。
二叉树的高度和宽度,有详细注释,数据结构课设时做的。
ppt画出了二叉树遍历的流程图流程图,设计先、中、后序的递归与非递归思想,即宽度优先的实现,详细对应遍历思想的代码实现见博客:https://blog.csdn.net/weixin_43763430/article/details/124417058