【数据结构】使用队列解决二叉树问题
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
执行流程如下:
-
初始化队列,将 A 入队 → 队列:[A]
-
队列非空,取出 A 并打印,将 B、C 入队 → 队列:[B, C],输出:A
-
队列非空,取出 B 并打印,将 D、E 入队 → 队列:[C, D, E],输出:A B
-
队列非空,取出 C 并打印,将 F 入队 → 队列:[D, E, F],输出:A B C
-
队列非空,取出 D 并打印,无子女入队 → 队列:[E, F],输出:A B C D
-
队列非空,取出 E 并打印,无子女入队 → 队列:[F],输出:A B C D E
-
队列非空,取出 F 并打印,无子女入队 → 队列:[],输出:A B C D E F
-
队列为空,循环结束,销毁队列
最终输结果为: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博客