Kotlin 面试算法实战：二叉树遍历与转换

3.3 如何从顶部开始逐层打印二叉树结点数据

面试题

难度系数	被考察系数
★★★☆☆	★★★★☆

给定一棵二叉树，要求逐层打印二叉树结点的数据，例如有如下二叉树：

对这棵二叉树层序遍历的结果为 1，2，3，4，5，6，7。

分析与解答：

为了实现对二叉树的层序遍历，就要求在遍历一个结点的同时记录下它的孩子结点的信息，然后按照这个记录的顺序来访问结点的数据。在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点，从而实现二叉树的层序遍历，遍历过程如下图所示：

在上图中，图（1）首先把根结点 1 放到队列里面，然后开始遍历。图（2）队列首元素（结点 1）出队列，同时它的孩子结点 2 和结点 3 进队列。图（3）接着出队列的结点为 2，同时把它的孩子结点 4 和结点 5 放到队列里，依此类推就可以实现对二叉树的层序遍历。

实现代码如下：

import java.util.LinkedList

/**
 * 用层序遍历的方式打印出二叉树结点的内容
 * @param root 二叉树根结点
 */
fun printTreeLayer(root: BiTNode?) {
    if (root == null) return
    var p: BiTNode?
    val queue = LinkedList<BiTNode>()
    // 树根结点进队列
    queue.offer(root)
    while (queue.size > 0) {
        p = queue.poll()
        // 访问当前结点
        print("${p.data} ")
        // 如果这个结点的左孩子不为空则入队列
        if (p.lChild != null) queue.offer(p.lChild)
        
         (p.rChild != ) queue.offer(p.rChild)
    }
}

 {
     arr = intArrayOf(, , , , , , , , , )
     root = arrayToTree(arr, , arr.size - ) 
    print()
    printTreeLayer(root)
}