【数据结构】使用队列解决二叉树问题

1.层序遍历

A先进队列，迭代-》队列不为空，拿出队头的数据然后将队头的左右节点放入队列，不断拿出放入，又队列满足先进先出的特性，无论这棵树多大都能实现层序遍历；

我们这里需要用到队列，可以在我的这篇文章中获取:

【数据结构】队列-CSDN博客

修改一下队列的数据类型

//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
        Queue q;
        QueueInit(&q);

        if (root == NULL)
                return;

        QueuePush(&q, root);  // 根节点先入队
        
        while (!QueueEmpty(&q))  // 队列不为空时循环
        {
            BTNode* front = QueueFront(&q);  // 获取队头节点
            
            QueuePop(&q);  // 队头节点出队
            
            printf("%c ", front->_data);  // 访问节点（打印数据）
            
            // 左右子节点入队（如果存在）
            if (front->_left)
                QueuePush(&q, front->_left);
            if (front->_right)
                QueuePush(&q, front->_right);
        }

        QueueDestroy(&q);
        printf("\n");
}

假设我们有如下二叉树：

        A
       / \
      B   C
     / \   \
    D   E   F

执行流程如下：

1. 初始化队列，将 A 入队 → 队列：[A]

2. 队列非空，取出 A 并打印，将 B、C 入队 → 队列：[B, C]，输出：A

3. 队列非空，取出 B 并打印，将 D、E 入队 → 队列：[C, D, E]，输出：A B

4. 队列非空，取出 C 并打印，将 F 入队 → 队列：[D, E, F]，输出：A B C

5. 队列非空，取出 D 并打印，无子女入队 → 队列：[E, F]，输出：A B C D

6. 队列非空，取出 E 并打印，无子女入队 → 队列：[F]，输出：A B C D E

7. 队列非空，取出 F 并打印，无子女入队 → 队列：[]，输出：A B C D E F

8. 队列为空，循环结束，销毁队列

最终输结果为：A B C D E F ，正好是按层序访问的结果。

2.判断二叉树是否为完全二叉树

遇到NULL就break跳出循环，然后接着判断剩下队列的数据，如果都是空，说明这个是完全二叉树；

//判断二叉树是否为满二叉树
//是返回1，不是返回0
int BinaryTreeComplete(BTNode* root)
{
        Queue q;
        QueueInit(&q);

        if (root == NULL)
                return;

        QueuePush(&q, root);

        while (!QueueEmpty(&q))
        {
                BTNode* front = QueueFront(&q);
                QueuePop(&q);

                if (front == NULL)
                {
                        break;
                }
                QueuePush(&q, front->_left);
                QueuePush(&q, front->_right);
        }

        while (!QueueEmpty(&q))
        {
                BTNode* front = QueueFront(&q);
                QueuePop(&q);

                if (front)
                {
                        QueueDestroy(&q);
                        return 0;
                }
                        
        }
        QueueDestroy(&q);
        return 1;
}

相关文章：

【数据结构】树的概念及结构-CSDN博客

【数据结构】二叉树概念及结构 -CSDN博客

【数据结构】堆-“此堆非比堆”-CSDN博客