为了实现对二叉树的层序遍历,就要求在遍历一个结点的同时记录下它的孩子结点的信息,然后按照这个记录的顺序来访问结点的数据,在实现的时候可以采用队列来存储当前遍历到的结点的孩子结点,从而实现二叉树的层序遍历,遍历过程如下图所示。
在上图中,图(1)首先把根结点1放到队列里面,然后开始遍历。图(2)队列首元素(结点1)出队列,同时它的孩子结点2和结点3进队列;图(3)接着出队列的结点为2,同时把它的孩子结点4和结点5放到队列里,依此类推就可以实现对二叉树的层序遍历。
实现代码如下:
package main
import(
."github.com/isdamir/gotype"
"fmt"
)
//方法功能:用层序遍历的方式打印出二叉树结点的内容
//输入参数:root二叉树根结点
func PrintTreeLayer(root*BNode){
if root==nil{
return
}
varp*BNode
queue:=NewSliceQueue()
//树根结点进队列
queue.EnQueue(root)
for queue.Size()>0{
p=queue.DeQueue().(*BNode)
//访问当前结点
fmt.Print(p.Data, "")
//如果这个结点的左孩子不为空则入队列
if p.LeflChild!=nil{
queue.EnQueue(p.LeftChild)
}
//如果这个结点的右孩子不为空则入队列
if p.RightChild!=nil{
queue.EnQueue(p.RightChild)
}
}
}
func main(){
data:=[]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
fmt.Println("数组:", data)
root:=ArrayToTree(data, 0, len(data)-1)
fmt.Print("树的层序遍历结果为:")
PrintTreeLayer(root)
fmt.Println()
}
程序的运行结果为
树的层序遍历结果为:6 3 9 2 5 8 10 14 7
算法性能分析: 在二叉树的层序遍历过程中,对树中的各个结点只进行了一次访问,因此,时间复杂度为O(n),此外,这种方法还使用了队列来保存遍历的中间结点,所使用队列的大小取决于二叉树中每一层中结点个数的最大值。具有N个结点的完全二叉树的深度为h=log
2n+1。而深度为h的这一层最多的结点个数为2
h-1=n/2。也就是说队列中可能的最多的结点个数为n/2。因此,这种算法的空间复杂度为O(n)。