二叉树层序遍历的回顾

电玩女神 2022-12-25 02:56 27阅读 0赞

## 一 概述 ##

二叉树层序遍历的过程需要借助队列来实现。

## 二 借助队列实现二叉树层序遍历的算法思想 ##

1.  初始将根入队并访问根结点；
2.  若有左子树，则将左子树的根入队；
3.  若有右子树，则将右子树的根入队；
4.  然后出队，访问该结点；
5.  反复该过程知道队列为空为止。

**如图：**

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70][]

**根据算法步骤队列的元素变化情况如下：**

**首先将根结点1入队：**

**接着将根结点1出队：**

**根结点1存在左子树，则将左子树的根入队：**

**根结点2存在右子树，则将右子树的根入队：**

**执行步骤4将结点2出队，然后继续步骤2和3：**

**执行步骤4将结点3出队，然后继续步骤2和3：**

**执行步骤4将结点4出队，然后继续步骤2和3：**

**执行步骤4将结点5出队，然后继续步骤2和3：**

**后续判断中由于结点5，6，7中都不存在左右子树，直接这些结点执行步骤4，完成出队操作。**

**最后根据中序遍历得到的遍历顺序为：1，2，3，4，5，6，7。**

## 三 二叉树中序遍历的重要代码 ##

void levelOrder(BiTree T) {
    	
    	//初始化一个队列
    	InitQueue(Q);
    	BiTree p;
    	//树的结点入队
    	EnQueue(Q,T);
    	while(!isEmpty(Q)){
    		//结点出队
    		Dequeue(Q,p);
    		//访问出队结点
    		visit(p);
    		//若有左子树，则将左子树的根入队；
    		if(p->lChild != NULL) {
    			EnQueue(Q,p->lChild);
    		}
    		//若有右子树，则将右子树的根入队；
    		if(p->rChild != NULL) {
    			Enqueue(Q,p->rChild);
    		}
    		//根据while循环可知，只要队列不空，上述步骤会一直循环。
    	}
    }

个人理解至此，后续有新的理解，再来补充。谢谢阅读！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NhbG1fZW5jb2Rl_size_16_color_FFFFFF_t_70]: /images/20221120/366c69402e93417591ea006e3ae7dfc8.png