做简历用哪个网站,网站 公司形象,工商查询系统,免费做app和网站的平台有哪些目录
实现思路
代码实现 之前介绍了二叉树的前、中、后序三种遍历#xff0c;采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑#xff0c;虽然实现方法并不难#xff0c;但是它所采取的思路是很值得学习的#xff0c;与前三者不同采用的是递归的方式。今天我们来学习另外一种遍历方式——层序遍历。层序遍历不容小觑虽然实现方法并不难但是它所采取的思路是很值得学习的与前三者不同我们将采用非递归的方式实现。
层序遍历从二叉树的根节点出发设根节点所在为第一层从上到下从左到右的一次访问第一、第二、第三......层的节点。
实现思路
我们将采用一种数据结构——队列来实现层序遍历。以这样的二叉树为例 我们知道队列有个重要的性质只能从队尾进数据在队头出数据
因此我们先将 1 入队。 接着让队头的元素 1 出队。在 1 出队的同时有个约定将 1 所在节点的左、右孩子入队 接着让队头的元素 2 出队。在 2 出队的同时将 2 所在节点的左、右孩子入队若为空节点则不入队 队头元素 4 出队左、右孩子入队 队头元素 3 出队左、右孩子入队 队头元素 5 出队左、右孩子入队
......
最后队列为空即表示所有节点都已访问完毕。 代码实现
因为此处用到了队列的知识若有不明白队列的童鞋可以去看看队列的概念结构实现【C语言版】小补一下哦。
//队列的初始化
void QueueInit(Queue* pq);
//释放malloc出的内存
void QueueDestroy(Queue* pq);
//入队
void QueuePush(Queue* pq, QDataType x);
//出队
void QueuePop(Queue* pq);
//获取队头的数据
QDataType QueueFront(Queue* pq);
//判断队列是否为空
bool QueueEmpty(Queue* pq);//层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(q);if (root)QueuePush(q, root);while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%d , front-data);QueuePop(q);if(front-left)QueuePush(q, front-left);if(front-right)QueuePush(q, front-right);}printf(\n);QueueDestroy(q);
}
