您现在的位置是:首页 >技术教程 >二叉树最大宽度-广度优先方式 -队列应用_20230520网站首页技术教程

二叉树最大宽度-广度优先方式 -队列应用_20230520

Jasonchen1224 2024-06-17 11:28:05
简介二叉树最大宽度-广度优先方式 -队列应用_20230520

二叉树最大宽度-广度优先(BFS)方式 -队列应用

  1. 前言

上一遍介绍了求解二叉树最大宽度的DFS解法,求解的核心主要是对根节点、左孩子及右孩子的宽度取最大值,通过赋值给根节点后,然后通过递归栈层层返回,当返回至树的根节点上的时候,求解出二叉树的最大宽度。其核心思想为DFS的后续遍历,对后续遍历的结果进行处理后,然后逐层返回。

本文探讨如何利用广度优先的方式求解二叉树的最大宽度,广度优先遍历通常配合队列一起进行,它的遍历方式同深度优先遍历不同,是按照逐层进行二叉树的遍历,直至最后一层遍历完成。

具体看一个例子,下图的二叉树,如果采用广度优先遍历的方式,

那么结点的遍历依次为①–>③–>②–>⑤–>⑦–>⑨,一般情况是需要借助队列的数据结构,通过不断的入队和出队,实现所有的遍历过程。

在这里插入图片描述

  1. 算法讨论

要通过BFS实现最大宽度的求解,我们需要按照二叉树的性质对存在的每个结点进行重新编号,如果根节点的编号定义为i,那么其左孩子编号定义为2*i, 右孩子的编号定义为2*i+1。不同于DFS的实现过程,可以采用递归变量对其编号进行保留记忆,在BFS算法中,我们需要对入队列的节点重新进行定义,它至少包含三个特性:

  • 二叉树结点本身
  • 二叉树结点所在的层次(深度)
  • 二叉树结点根据上述定义,计算出来的编号

根据上述数据特征,可以定义一个结构体,作为队列里的基本元素,随着BFS的不断进行,我们不断进行入队和出队的相应操作,操作过程中,不断对其三个特性进行相关的赋值操作。

实际操作过程中,需要对最左端的非空结点的序列号进行保存,作为后续同一层宽度计算的基础点;如果从出队的元素的层次号(深度)发生变化,此时需要更新最左侧的结点序列号,以确保另外一层的结点的基准正确。实际操作过程中,可以采用变量交替的方式实现这个操作。

我们可以对每个结点的宽度进行比较,选取最大的值进行返回,就可以求助整棵二叉树的最大宽度。

  1. 具体代码

由于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
  1. 小结

通过本示例学习,加深了对BFS遍历的深入理解,也灵活对原有二叉树的结点进行增强,进行出队/入队的相关操作,最终求得所需结果。

参考资料:

662. 二叉树最大宽度 - 力扣(Leetcode)

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。