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

二叉树最大宽度-广度优先(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\n");
    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\n");
    getchar();
    fclose(fp);
    return EXIT_SUCCESS;
}

#endif