您现在的位置是:首页 >技术教程 >二叉树最大宽度-广度优先方式 -队列应用_20230520网站首页技术教程
二叉树最大宽度-广度优先方式 -队列应用_20230520
二叉树最大宽度-广度优先(BFS)方式 -队列应用
- 前言
上一遍介绍了求解二叉树最大宽度的DFS解法,求解的核心主要是对根节点、左孩子及右孩子的宽度取最大值,通过赋值给根节点后,然后通过递归栈层层返回,当返回至树的根节点上的时候,求解出二叉树的最大宽度。其核心思想为DFS的后续遍历,对后续遍历的结果进行处理后,然后逐层返回。
本文探讨如何利用广度优先的方式求解二叉树的最大宽度,广度优先遍历通常配合队列一起进行,它的遍历方式同深度优先遍历不同,是按照逐层进行二叉树的遍历,直至最后一层遍历完成。
具体看一个例子,下图的二叉树,如果采用广度优先遍历的方式,
那么结点的遍历依次为①–>③–>②–>⑤–>⑦–>⑨,一般情况是需要借助队列的数据结构,通过不断的入队和出队,实现所有的遍历过程。
- 算法讨论
要通过BFS实现最大宽度的求解,我们需要按照二叉树的性质对存在的每个结点进行重新编号,如果根节点的编号定义为i,那么其左孩子编号定义为2*i, 右孩子的编号定义为2*i+1。不同于DFS的实现过程,可以采用递归变量对其编号进行保留记忆,在BFS算法中,我们需要对入队列的节点重新进行定义,它至少包含三个特性:
- 二叉树结点本身
- 二叉树结点所在的层次(深度)
- 二叉树结点根据上述定义,计算出来的编号
根据上述数据特征,可以定义一个结构体,作为队列里的基本元素,随着BFS的不断进行,我们不断进行入队和出队的相应操作,操作过程中,不断对其三个特性进行相关的赋值操作。
实际操作过程中,需要对最左端的非空结点的序列号进行保存,作为后续同一层宽度计算的基础点;如果从出队的元素的层次号(深度)发生变化,此时需要更新最左侧的结点序列号,以确保另外一层的结点的基准正确。实际操作过程中,可以采用变量交替的方式实现这个操作。
我们可以对每个结点的宽度进行比较,选取最大的值进行返回,就可以求助整棵二叉树的最大宽度。
- 具体代码
由于C语言中没有提供队列的关键实现函数,读者可以参考《数据结构》(严蔚敏)里面的介绍自行实现,本文应用到的队列的实现方式介绍来自此教材。
上面提到,我们需要定义队列的结点,以便涵盖更多的信息,利于出队/入队的相关操作,定义新的结构体作为队列的基本元素。在TriNode结构体当中,容易发现node指针保存二叉树中遍历到的当前的指针,index保留当前结点的编号,它根据其父节点编号计算而成,在入队时自动生成,depth变量保存当前结点所在的层次(深度),如果出队的元素的层次有变化,我们需要对index重新进行赋值,作为当前层(深度)的基准点,以便正确计算后面元素的宽度(宽度跨度)。
typedef struct BiTNode
{
int val;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
typedef struct TriNode
{
BiTNode *node;
int index;
int depth;
}TriNode;
3.1 头文件
/**
* @file max_width.h
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-05-20
*
* @copyright Copyright (c) 2023
*
*/
#ifndef MAX_WIDTH_H
#define MAX_WIDTH_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#define MAX(a, b) ((a) > (b) ? (a) : (b))
typedef struct BiTNode
{
int val;
struct BiTNode *lchild;
struct BiTNode *rchild;
} BiTNode, *BiTree;
typedef struct TriNode
{
BiTNode *node;
int index;
int depth;
}TriNode;
typedef TriNode QElemType_L;
#include "../../../../Data_Structure_TingHua University/Textbook/ch03/07_LinkQueue/LinkQueue.c"
void create_bitree(BiTree *T, FILE *fp);
int max_width_of_binary_tree(BiTree root);
#endif
3.2 函数实现
可以返现实现本问题的关键函数为max_width_of_binary_tree,我们首先定义变量queue并对其进行初始化,初始化完成后,我们对根节点、结点编号、层数构成的结构体进行入队操作。值得一提的是,我们分别定义了depth和index,可以理解为动态出队的结点层数和结点编号,同时定义了pre_depth和pre_index分别代表当前的层数和最左侧非空结点的编号(基准点)。
然后利用循环语句对二叉树里面的元素进行出栈和入栈操作,先进行出栈操作,并判断出栈的结点是否为某层的最左端的第一个非空结点,如果满足这个条件,我们就对pre_depth和pre_index进行更新分别记录当前的层数和最左侧非空结点的编号。
最后对二叉树的左右子树分别进行检查,如果为非空结点,那么就按照上面提到的新节点的三个特性,构建一个新的队列结点进行入队操作,由于队列的特性,我们先处理左孩子结点,后处理右孩子结点。
重复上述操作直至队列里面的元素为空,此时就代表我们遍历完成所有的二叉树结点,并且对每个结点的宽度进行了计算和比较,已经获得了最大宽度值。
/**
* @file max_width.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-05-20
*
* @copyright Copyright (c) 2023
*
*/
#ifndef MAX_WIDTH_C
#define MAX_WIDTH_C
#include "max_width.h"
int max_width_of_binary_tree(BiTree root)
{
int depth;
int index;
int pre_depth;
int pre_index;
int res;
BiTree p;
TriNode node;
LinkQueue queue;
InitQueue(&queue);
node.depth=1;
node.index=1;
node.node=root;
EnQueue(&queue,node);
pre_depth=pre_index=0;
res=0;
while(!QueueEmpty(queue))
{
DeQueue(&queue,&node);
depth=node.depth;
index=node.index;
if(depth>pre_depth)
{
pre_depth=depth;
pre_index=index;
}
res=MAX(res,index-pre_index+1);
if(node.node->lchild)
{
EnQueue(&queue, (TriNode){node.node->lchild, index * 2, depth + 1});
}
if (node.node->rchild)
{
EnQueue(&queue, (TriNode){node.node->rchild, index * 2 + 1, depth + 1});
}
}
return res;
}
void create_bitree(BiTree *T, FILE *fp)
{
int val;
// printf("Please input the integer
");
fscanf(fp, "%d", &val); // 1,2,3,-1,-1,4,-1,-1,2,4,-1,-1,3,-1,-1
if (val == -1)
{
*T = NULL;
}
else
{
*T = (BiTree)malloc(sizeof(BiTNode));
(*T)->val = val;
create_bitree(&((*T)->lchild), fp);
create_bitree(&((*T)->rchild), fp);
}
return;
}
#endif
3.3 测试函数
/**
* @file max_width_main.c
* @author your name (you@domain.com)
* @brief
* @version 0.1
* @date 2023-05-20
*
* @copyright Copyright (c) 2023
*
*/
#ifndef MAX_WIDTH_MAIN_C
#define MAX_WIDTH_MAIN_C
#include "max_width.c"
int main(void)
{
BiTree root;
int max_width;
FILE *fp;
fp = fopen("data.txt", "r");
create_bitree(&root, fp);
max_width=max_width_of_binary_tree(root);
printf("The actions had been done
");
getchar();
fclose(fp);
return EXIT_SUCCESS;
}
#endif
测试数据data.txt文件
1
3
5
-1
-1
7
-1
-1
2
-1
9
-1
-1
- 小结
通过本示例学习,加深了对BFS遍历的深入理解,也灵活对原有二叉树的结点进行增强,进行出队/入队的相关操作,最终求得所需结果。
参考资料: