【PTA】4-1 计算二叉树最大的宽度 【数据结构】

二叉树的最大宽度是指二叉树所有层中结点个数的最大值。例如：下面二叉树的宽度为4.

输入二叉树的完全前序序列建立一棵二叉树（上机作业2：二叉树的建立和遍历），编写算法计算并输出二叉树的宽度。

输入格式:

二叉树数据元素为单个字符且各不相同，取值范围为A~Z，a~z，二叉树可以为空。输入数据分为2行，第1行为二叉树完全前序序列字符(包括#)个数，第2行为二叉树的完全前序序列。例如，上面二叉树的输入为：ABD##FE###CG#H##I##，其中#代表为空的位置。

输出格式:

输出一行，二叉树的宽度（整数）

输入样例:

以上面的二叉树为例，输入为：

19
ABD##FE###CG#H##I##

输出样例:

对于上面的输入，输出为：

4

下面是分析过程： 

求一个二叉树的最大宽度，不难想到层次遍历的方法，就是构建队列，采用入队，出队的方式来寻找二叉树的最大宽度

既然是二叉树了，那一定是基于基本树形结构来实现的，所以我们要先构建一个树的结构体

struct BinTree 
{
    char data;
    BinTree *lchild; // 左孩子
    BinTree *rchild; // 右孩子
};
typedef BinTree* ElemType;

 解释一下：
在C++编程语言中，typedef 关键字用于创建一个新的类型名，它是对现有类型的别名。
这一行的作用是声明 ElemType 是一个指向 BinTree 类型的对象的指针类型。换句话说，ElemType 就相当于 BinTree*。

我们刚才说，要用队列辅助实现，于是，构建一个队列 

typedef struct SqQueue 
{
    ElemType data[MAXSIZE];
    int front, rear;
} SqQueue;

 队列首先需要初始化：

void InitQueue(SqQueue &Q) 
{
    Q.rear = Q.front = 0;
}

其次，我们需要在此基础上判断队列的状态，比如队列是否为空，是否已满： 

// 判断队列是否为空
bool QueueEmpty(SqQueue Q) 
{
    return Q.rear == Q.front;
}

// 判断队列是否已满
bool QueueFull(SqQueue Q) 
{
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

在这里我解释一下思想：
1.Q.front == Q.rear成立，该条件可以用作判断队空的条件
2.不能用rear == MAXSIZE来判断是否队满，因为front不为0，但rear == MAXSIZE时，队列不满，但是 rear == MAXSIZE条件成立，这时会发生“假溢出”。

3.为了更加准确的判断是否队满，我们在入队时少用一个数据元素空间，以队尾指针 +1 等于队头指针判读队满
所以，队满条件是：(Q.rear + 1) % MAXSIZE == Q.front
这里就有循环队列，即环状结构的意思了

接下来是入队操作： 

void EnQueue(SqQueue &Q, BinTree *x) 
{
    if (!QueueFull(Q)) 
	{ // 如果队列未满
        Q.data[Q.rear] = x; // 将指向 BinTree 的指针存入队尾
        Q.rear = (Q.rear + 1) % MAXSIZE; // 移动队尾指针
    }
}
  • 函数接受一个参数SqQueue &Q，这是一个顺序队列的引用，通过引用传递可以直接修改传入的队列对象而无需返回值来更新队列状态。另一个参数BinTree *x是一个指向二叉树节点的指针，这表示要入队的元素是一个指向二叉树节点的指针。
  • Q.data[Q.rear] = x：将指向二叉树节点的指针x存入队尾，这里Q.data是顺序队列中存储元素的数组，Q.rear表示队尾的位置。
  • Q.rear = (Q.rear + 1) % MAXSIZE：更新队尾指针，将队尾指针向后移动一位。由于队列是循环队列，使用取模运算% MAXSIZE确保队尾指针在队列的有效范围内循环移动。如果队尾指针到达队列的末尾，下一个位置将回到队列的开头。

然后是出队操作： 

 

void DeQueue(SqQueue &Q, BinTree *&x) 
{
    if (!QueueEmpty(Q)) 
	{ // 如果队列非空
        x = Q.data[Q.front]; // 获取指向 BinTree 的指针
        Q.front = (Q.front + 1) % MAXSIZE; // 移动队头指针
    }
}
  • 这个函数的作用是从顺序队列Q中出队一个元素，并将出队的元素（指向二叉树节点的指针）赋值给外部传入的指针x
  • x = Q.data[Q.front]：将队头位置的元素（指向二叉树节点的指针）赋值给外部传入的指针x，这样外部就可以获取出队的元素。这里Q.data是顺序队列中存储元素的数组，Q.front表示队头的位置。
  • Q.front = (Q.front + 1) % MAXSIZE：更新队头指针，将队头指针向后移动一位。由于队列是循环队列，使用取模运算% MAXSIZE确保队头指针在队列的有效范围内循环移动。如果队头指针到达队列的末尾，下一个位置将回到队列的开头。

 先序遍历创建一个二叉树：

BinTree *CreateBinTree() 
{
    char ch;
    cin >> ch;
    if (ch == '#') 
	{
        return nullptr;
    } 
	else 
	{
        BinTree *T = new BinTree;
        T->data = ch;
        T->lchild = CreateBinTree();
        T->rchild = CreateBinTree();
        
        return T;
    }
}
  • BinTree *T = new BinTree;：创建一个新的二叉树节点。
  • T->data = ch;：将读取的字符赋值给新节点的数据域。
  • T->lchild = CreateBinTree();：递归调用CreateBinTree函数创建当前节点的左子树，并将返回的指针赋值给当前节点的左孩子指针。
  • T->rchild = CreateBinTree();：递归调用CreateBinTree函数创建当前节点的右子树，并将返回的指针赋值给当前节点的右孩子指针。

 

然后是层次遍历： 

void LevelOrder(BinTree *T) 
{
    SqQueue Q;
    InitQueue(Q);
    if (T != nullptr) 
	{
        EnQueue(Q, T); // 入队根节点
    }
    while (!QueueEmpty(Q)) 
	{
        BinTree *x;
        DeQueue(Q, x); // 出队并获取指向 BinTree 的指针
        if (x->lchild != nullptr) 
		{
            EnQueue(Q, x->lchild); // 入队左子节点
        }
        if (x->rchild != nullptr) 
		{
            EnQueue(Q, x->rchild); // 入队右子节点
        }
    }
}
  • while (!QueueEmpty(Q))：当队列不为空时，持续进行以下操作，以确保遍历完所有节点。
  • BinTree *x;：声明一个指向二叉树节点的指针x，用于存储从队列中出队的节点。
  • DeQueue(Q, x);：从队列中出队一个节点，并将其指针存储在x中。
  • if (x->lchild!= nullptr)：如果出队节点的左子节点不为空，则将左子节点入队，以便后续访问。
  • EnQueue(Q, x->lchild);：将左子节点入队。
  • if (x->rchild!= nullptr)：如果出队节点的右子节点不为空，则将右子节点入队，以便后续访问。
  • EnQueue(Q, x->rchild);：将右子节点入队。

 最后，就是本题的核心：计算二叉树的最大宽度

int WidthBinTree(BinTree *T) 
{
    // 创建一个队列对象，用于存储待访问的节点。
    SqQueue Q;
    // 初始化队列。
    InitQueue(Q);

    // 初始化最大宽度变量。
    int maxWidth = 0;
    // 初始化当前层节点的数量。
    int currentLayerNodes = 0;
    // 初始化下一层节点的数量。
    int nextLayerNodes = 0;

    // 如果根节点不为空，则将其加入队列。
    if (T != nullptr) 
	{
        EnQueue(Q, T); // 入队根节点
        currentLayerNodes++; // 根节点算作第一层的一个节点
    }

    // 当队列不为空时继续循环。
    while (!QueueEmpty(Q)) 
	{
        // 处理当前层的所有节点。
        for(int i=0; i<currentLayerNodes; ++i) 
		{
            // 出队一个节点，并获取其指向的二叉树节点。
            BinTree *x;
            DeQueue(Q, x); // 出队并获取指向 BinTree 的指针
            
            // 更新最大宽度。
            maxWidth = max(maxWidth, currentLayerNodes);

            // 如果当前节点有左子节点，则将左子节点加入队列。
            if (x->lchild != nullptr) 
			{
                EnQueue(Q, x->lchild); // 入队左子节点
                nextLayerNodes++; // 计数下一层的节点
            }
            // 如果当前节点有右子节点，则将右子节点加入队列。
            if (x->rchild != nullptr) 
			{
                EnQueue(Q, x->rchild); // 入队右子节点
                nextLayerNodes++; // 计数下一层的节点
            }
        }
        
        // 准备处理下一层。
        currentLayerNodes = nextLayerNodes;
        nextLayerNodes = 0;
    }

    // 返回计算得到的最大宽度值。
    return maxWidth;
}

 最后，我们把完整代码写出来

#include <iostream>
#include <queue>
#include <string>
using namespace std;

// 定义树的结构体
struct BinTree 
{
    char data;
    BinTree *lchild; // 左孩子
    BinTree *rchild; // 右孩子
};

// 定义队列元素类型为指向 BinTree 的指针
typedef BinTree* ElemType;

#define MAXSIZE 1000

// 定义队列结构
typedef struct SqQueue 
{
    ElemType data[MAXSIZE];
    int front, rear;
} SqQueue;

// 初始化队列
void InitQueue(SqQueue &Q) 
{
    Q.rear = Q.front = 0;
}

// 判断队列是否为空
bool QueueEmpty(SqQueue Q) 
{
    return Q.rear == Q.front;
}

// 判断队列是否已满
bool QueueFull(SqQueue Q) 
{
    return (Q.rear + 1) % MAXSIZE == Q.front;
}

// 入队操作
void EnQueue(SqQueue &Q, BinTree *x) 
{
    if (!QueueFull(Q)) 
	{ // 如果队列未满
        Q.data[Q.rear] = x; // 将指向 BinTree 的指针存入队尾
        Q.rear = (Q.rear + 1) % MAXSIZE; // 移动队尾指针
    }
}

// 出队操作
void DeQueue(SqQueue &Q, BinTree *&x) 
{
    if (!QueueEmpty(Q)) 
	{ // 如果队列非空
        x = Q.data[Q.front]; // 获取指向 BinTree 的指针
        Q.front = (Q.front + 1) % MAXSIZE; // 移动队头指针
    }
}

BinTree *CreateBinTree() 
{
    char ch;
    cin >> ch;
    if (ch == '#') 
	{
        return nullptr;
    } 
	else 
	{
        BinTree *T = new BinTree;
        T->data = ch;
        T->lchild = CreateBinTree();
        T->rchild = CreateBinTree();
        
        return T;
    }
}

// 层次遍历
void LevelOrder(BinTree *T) 
{
    SqQueue Q;
    InitQueue(Q);
    if (T != nullptr) 
	{
        EnQueue(Q, T); // 入队根节点
    }
    while (!QueueEmpty(Q)) 
	{
        BinTree *x;
        DeQueue(Q, x); // 出队并获取指向 BinTree 的指针
        if (x->lchild != nullptr) 
		{
            EnQueue(Q, x->lchild); // 入队左子节点
        }
        if (x->rchild != nullptr) 
		{
            EnQueue(Q, x->rchild); // 入队右子节点
        }
    }
}

int WidthBinTree(BinTree *T) 
{
    // 创建一个队列对象，用于存储待访问的节点。
    SqQueue Q;
    // 初始化队列。
    InitQueue(Q);

    // 初始化最大宽度变量。
    int maxWidth = 0;
    // 初始化当前层节点的数量。
    int currentLayerNodes = 0;
    // 初始化下一层节点的数量。
    int nextLayerNodes = 0;

    // 如果根节点不为空，则将其加入队列。
    if (T != nullptr) 
	{
        EnQueue(Q, T); // 入队根节点
        currentLayerNodes++; // 根节点算作第一层的一个节点
    }

    // 当队列不为空时继续循环。
    while (!QueueEmpty(Q)) 
	{
        // 处理当前层的所有节点。
        for(int i=0; i<currentLayerNodes; ++i) 
		{
            // 出队一个节点，并获取其指向的二叉树节点。
            BinTree *x;
            DeQueue(Q, x); // 出队并获取指向 BinTree 的指针
            
            // 更新最大宽度。
            maxWidth = max(maxWidth, currentLayerNodes);

            // 如果当前节点有左子节点，则将左子节点加入队列。
            if (x->lchild != nullptr) 
			{
                EnQueue(Q, x->lchild); // 入队左子节点
                nextLayerNodes++; // 计数下一层的节点
            }
            // 如果当前节点有右子节点，则将右子节点加入队列。
            if (x->rchild != nullptr) 
			{
                EnQueue(Q, x->rchild); // 入队右子节点
                nextLayerNodes++; // 计数下一层的节点
            }
        }
        
        // 准备处理下一层。
        currentLayerNodes = nextLayerNodes;
        nextLayerNodes = 0;
    }

    // 返回计算得到的最大宽度值。
    return maxWidth;
}

int main() 
{
    int n;
    cin >> n;
    string preorder;   
    BinTree *T = CreateBinTree();
    cout << WidthBinTree(T) << endl; 
    return 0;
}

 

 

 

 

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/904969.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

开源智能文档处理系统，助力医疗数据精准管理与高效整合

开源智能文档处理系统，助力医疗数据精准管理与高效整合

问题导向&#xff1a; 当前医疗文档中信息零散、数据整合度低&#xff0c;导致人工管理难度加大&#xff0c;错误率高。思通数科的系统在此背景下提供了免费的开源工具&#xff0c;帮助医疗机构实现数据的高效、精准管理&#xff0c;支持实时数据提取和智能管理。 客户案例&am…
阅读更多...
STM32使用串口下载程序

STM32使用串口下载程序

STM32使用串口下载程序 FluMcu软件下载地址 单片机在线编程网 STM32 MCU启动模式配置(Boot Configuration) 单片机复位后&#xff0c;SYSCLK的第4个上升沿&#xff0c;BOOT引脚上的值将锁存&#xff0c;用户可以通过设置BOOT0和BOOT1引脚的值&#xff0c;来选择复位后的启动…
阅读更多...
新兴斗篷cloak技术，你了解吗？

新兴斗篷cloak技术，你了解吗？

随着互联网技术的飞速发展&#xff0c;网络营销领域也经历了翻天覆地的变革。 从最早的网络横幅广告到如今主流的搜索引擎和社交媒体营销&#xff0c;广告形式变得越来越多样。 其中&#xff0c;搜索引擎广告一直以其精准投放而备受青睐&#xff0c;但近年来&#xff0c;一项名…
阅读更多...
WPF+MVVM案例实战（十四）- 封装一个自定义消息弹窗控件（下）

WPF+MVVM案例实战（十四）- 封装一个自定义消息弹窗控件（下）

文章目录 1、案例效果2、弹窗空间使用1.引入用户控件2、按钮命令实现 3、总结4、源代码获取 1、案例效果 2、弹窗空间使用 1.引入用户控件 打开 Wpf_Examples 项目&#xff0c;在引用中添加用户控件库&#xff0c;在 MainWindow.xaml 界面引用控件库&#xff0c;代码如下&…
阅读更多...
教材管理系统设计与实现

教材管理系统设计与实现

教材管理系统设计与实现 1. 系统概述 教材管理系统是一个基于PHP和SQL的Web应用程序&#xff0c;旨在为学校提供一个高效的教材管理平台。该系统可以帮助管理员录入教材信息、教师查询和申请教材、学生查询教材信息&#xff0c;提高教材管理的效率和透明度。 2. 技术栈 前端…
阅读更多...
【时间序列分析】平稳时间序列分析——Wold分解定理和延迟算子

【时间序列分析】平稳时间序列分析——Wold分解定理和延迟算子

Wold分解定理 &#xff08;这个定理是平稳时间序列分析的理论基石。&#xff09; 对于任意一个离散平稳时间序列, 它都可以分解为两个不相关的平稳序列之和, 其中一个为确定性的 (deterministic), 另一个为随机性的(stochastic) xₜVₜξₜ&#xff0c;{V₁} 为确定性平稳序列…
阅读更多...
基于SpringBoot的汽车配件销售管理系统

基于SpringBoot的汽车配件销售管理系统

作者&#xff1a;计算机学姐 开发技术&#xff1a;SpringBoot、SSM、Vue、MySQL、JSP、ElementUI、Python、小程序等&#xff0c;“文末源码”。 专栏推荐&#xff1a;前后端分离项目源码、SpringBoot项目源码、Vue项目源码、SSM项目源码、微信小程序源码 精品专栏&#xff1a;…
阅读更多...
数图携手黄商集团，打造品类空间精细化管理体系！

数图携手黄商集团，打造品类空间精细化管理体系！

数图合作伙伴又1 在这秋高气爽的时节&#xff0c;满怀激情地传递着喜人的消息&#xff1a;数图的合作伙伴队伍再次壮大。位于湖北黄冈的黄商集团&#xff0c;勇于拥抱时代发展的数字变革潮流&#xff0c;积极致力于探索精细化的品类空间管理之道&#xff0c;一步一个脚印&…
阅读更多...
大模型日报｜3 篇必读的大模型论文

大模型日报｜3 篇必读的大模型论文

大家好&#xff0c;今日必读的大模型论文来啦&#xff01; 1.SocialGPT&#xff1a;贪婪分段提示优化实现社会关系推理 社会关系推理旨在从图像中识别朋友、配偶和同事等关系类别。虽然目前的方法采用了使用标注图像数据端到端训练专用网络的模式&#xff0c;但这些方法在通用…
阅读更多...
Unity计算二维向量夹角余弦值和正弦值的优化方法参考

Unity计算二维向量夹角余弦值和正弦值的优化方法参考

如果不考虑优化问题&#xff0c;计算两个向量的余弦值或者正弦值可以直接使用类似的方法&#xff1a; [SerializeField] Vector2 v1, v2;void Start() {float valCos Mathf.Acos(Vector2.SignedAngle(v1, v2));float valSin Mathf.Asin(Vector2.SignedAngle(v1, v2)); } 但是…
阅读更多...
利用EasyExcel实现简易Excel导出

利用EasyExcel实现简易Excel导出

目标 通过注解形式完成对一个方法返回值的通用导出功能 工程搭建 pom <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance&qu…
阅读更多...
Spring Boot框架：校园社团信息管理的现代化解决方案

Spring Boot框架：校园社团信息管理的现代化解决方案

3系统分析 3.1可行性分析 通过对本校园社团信息管理系统实行的目的初步调查和分析&#xff0c;提出可行性方案并对其一一进行论证。我们在这里主要从技术可行性、经济可行性、操作可行性等方面进行分析。 3.1.1技术可行性 本校园社团信息管理系统采用SSM框架&#xff0c;JAVA作…
阅读更多...
基于SpringBoot+Vue的前后端分离的大学自动排课系统

基于SpringBoot+Vue的前后端分离的大学自动排课系统

✌全网粉丝20W,csdn特邀作者、博客专家、CSDN新星计划导师、java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取项目下载方式&#x1f345; 一、项目背景介绍&#xff1a; 在这个背景下&#xf…
阅读更多...
探索无线网IP地址：定义、修改方法及实践指南

探索无线网IP地址：定义、修改方法及实践指南

在数字化时代&#xff0c;无线网络已成为我们日常生活和工作中不可或缺的一部分。它让我们能够随时随地接入互联网&#xff0c;享受信息交流的便利。然而&#xff0c;对于无线网络背后的技术细节&#xff0c;如IP地址&#xff0c;许多用户可能并不十分了解。IP地址&#xff0c;…
阅读更多...
Spring IoC——IoC 容器的使用

Spring IoC——IoC 容器的使用

1. 应用分层 应用分层是一种软件开发设计思想&#xff0c;它将应用程序分成 N 个层次&#xff0c;这 N 个层次分别负责各自的职责&#xff0c;多个层次之间协同提供完整的功能&#xff0c;根据项目的复杂度&#xff0c;可以分成三层&#xff0c;四层或更多层&#xff0c;MVC 就…
阅读更多...
人工智能进程；算子加速的具体计算部分；大模型GPT5：参数18万亿；大模型面临问题

人工智能进程；算子加速的具体计算部分；大模型GPT5：参数18万亿；大模型面临问题

目录 人工智能进程 算子加速的简单理解，举例说明 一、简单理解 二、举例说明 一、算子加速的具体计算部分 二、举例说明 三、算子加速是否仅针对GPU 大模型GPT5：参数18万亿 大模型面临问题 算力集群设计框架 人工智能进程
阅读更多...
深入理解Java集合：从基础到高级应用

深入理解Java集合：从基础到高级应用

深入理解Java集合&#xff1a;从基础到高级应用 1. 数组与集合的区别 1.1 相同点 数组和集合都是用于存储多个数据的容器&#xff0c;但它们的使用场景和特性各有不同。 1.2 不同点 长度&#xff1a;数组的长度在创建时就固定了&#xff0c;而集合的长度是动态可变的&…
阅读更多...
【自动化测试之oracle数据库】MacOs如何安装oracle- client

【自动化测试之oracle数据库】MacOs如何安装oracle- client

操作系统为Mac OS&#xff0c;本地在pycharm上跑自动化脚本时&#xff0c;因为有操作oracle数据库的部分&#xff0c;所以需要安装oracle数据库的客户端&#xff0c;并install cx_oracle,本文主要介绍如何在macOS上完成安装&#xff0c;并在python自动化测试代码中配置&#xf…
阅读更多...
如何在vscode中使用鼠标滑轮滚动来改变字体大小

如何在vscode中使用鼠标滑轮滚动来改变字体大小

实现内容&#xff1a;如何在vscode中使用鼠标滑轮滚动来改变字体大小 使用场景&#xff1a;我是在Ubuntu中安装的vscode 需求&#xff1a;因为最近在用这个&#xff0c;但是在使用过程中发现vscode的字体大小有点小&#xff0c;所以想改变下 实现滚轮滑动改变字体大小的具体步…
阅读更多...
鸿蒙NEXT应用上架与分发步骤详解

鸿蒙NEXT应用上架与分发步骤详解

大家好&#xff0c;我是 V 哥。今天的文章来聊一聊HarmonyOS NEXT应用上架。当你开发、调试完HarmonyOS应用/元服务&#xff0c;就可以前往AppGallery Connect申请上架&#xff0c;华为审核通过后&#xff0c;用户即可在华为应用市场获取您的HarmonyOS应用/元服务。 V 哥推荐&a…
阅读更多...
最新文章

Copyright @ 2022~2023