层序遍历二叉树

队列一大用处就是实现二叉树的层序遍历，将存在的左右子节点均加入队列，然后继续队头遍历。
image.png
golang实现

  1. type Node struct {
  2.     Left  *Node
  3.     Right *Node
  4.     Data  interface{}
  5. }
  8. func main() {
  9.     // 构造二叉树
  10.     n1 := Node{Data: "1"}
  11.     n2 := Node{Data: "2"}
  12.     n3 := Node{Data: "3"}
  13.     n4 := Node{Data: "4"}
  14.     n5 := Node{Data: "5"}
  15.     n7 := Node{Data: "7"}
  16.     n1.Left = &n2
  17.     n1.Right = &n3
  18.     n2.Left = &n4
  19.     n2.Right = &n5
  20.     n3.Right = &n7
  22.     // 遍历二叉树, 定义切片表示队列，加入根节点
  23.     queue := []*Node{&n1}
  24.     // 最终结果
  25.     var result []*Node
  26.     // 循环处理
  27.     for true {
  28.         // 将左子节点加入队列
  29.         if queue[0].Left != nil {
  30.             queue = append(queue, queue[0].Left)
  31.         }
  32.         // 将右子节点加入队列
  33.         if queue[0].Right != nil {
  34.             queue = append(queue, queue[0].Right)
  35.         }
  36.         // 当前节点加入结果
  37.         result = append(result, queue[0])
  38.         // 队列中是否还有剩余节点
  39.         if len(queue) > 1 {
  40.             // 截取剩余节点
  41.             queue = queue[1:]
  42.         } else {
  43.             // 队列中没有剩余节点了
  44.             break
  45.         }
  46.     }
  48.     // 遍历结果
  49.     for _, ele := range result {
  50.         fmt.Print(ele.Data, " ")
  51.     }
  52. }

结果和图示一致

1 2 3 4 5 7