【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中出队一个元素，并将出队的元素（指向二叉树节点的指针）赋值给外部传入的指针xx = 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;
}
更多推荐
29
0- 0
已为社区贡献2条内容
所有评论(0)