【数据结构】二叉树——层序遍历

【数据结构】二叉树——层序遍历

引用

CSDN

1.

https://m.blog.csdn.net/2302_79968411/article/details/143471898

二叉树的层序遍历是数据结构中的一个重要概念，它体现了广度优先搜索的思想。本文将详细介绍层序遍历的两种实现方式：递归和非递归，并分析它们各自的优缺点。

层序遍历

层序遍历是一种广度优先遍历方式，按照二叉树的深度一层一层进行遍历。

以图上二叉树为例，层序遍历的顺序为：A B C D E F G H。

二、层序遍历（递归）

若用递归方式解决层序遍历，我们可以先算出二叉树的深度，然后按照不同深度 k 进行遍历。每次向下遍历就 k–，当 k == 1 时就是第 k 层的数据，以此来实现层序遍历。

//层序遍历(1)
//(先写一个可以遍历某一层的函数，再循环遍历每一层)
//某一层遍历
void BTLevelkOrder(BTNode* php, int k)
{
    if (php == NULL || k == 0)
    {
        return;
    }
    if (k == 1)
    {
        printf("%c ", php->val);
    }
    BTLevelkOrder(php->left, k - 1);
    BTLevelkOrder(php->right, k - 1);
}
//层序遍历二叉树
void BTLevelOrder(BTNode* php)
{
    if (php == NULL)
    {
        return;
    }
    int dep = BTLevelDepth(php);
    for (int i = 1; i <= dep; i++)
    {
        BTLevelkOrder(php, i);
    }
}

三、层序遍历（非递归）

若要用非递归的方式来解决层序遍历，我们先将根节点入队列，然后将根节点出队列，并将该根节点的左右节点人队列，重复该过程，直到队列为空。

//层序遍历(2)
//将节点地址依次入队列
void BTLevelOrder(BTNode* php)
{
    //创建队列
    Queue p;
    QueueInit(&p);
    //先将根入队列
    if(php)
        QueuePush(&p, php);
    while (!QueueEmpty(&p))
    {
        //将根位置节点出队列
        QueueDateType cp = QueueFront(&p);
        QueuePop(&p);
        //打印出队列节点的数据
        printf("%c ", cp->val);
        //左右节点不为空入队列
        if (cp->left)
        {
            QueuePush(&p, cp->left);
        }
        if (cp->right)
        {
            QueuePush(&p, cp->right);
        }
    }
    //队列销毁
    QueueDesTroy(&p);
}

四、总结

上面我们学习了递归与非递归的方式去对二叉树进行层序遍历。我们发现递归的代码简介，而且好理解。那我们为什么不用递归而会去研究非递归的方式呢？因为我们的递归过程会重复调用函数，就会在栈上开辟空间。而栈中空间大小是有限的。若我们的递归深度太深就会有栈溢出的风险。而非递归方式开辟的队列是在堆中开辟的空间会大很多，一般不会出现空间被占满的情况。