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

一、层序遍历

层序遍历是一种广度优先遍历

以图上二叉树为例，层序遍历就是按照二叉树的深度一层一层进行遍历
遍历顺序：

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);
}

四、总结

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