image.png
递归实现

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层序遍历

    层序遍历： 按照二叉树中的层次从左到右依次遍历每层中的结点 借助队列先进先出的特性，从树的根结点开始，依次将其左子节点和右子节点入队。 而后每次队列中一个结点出队，都将其左子节点和右子节点入队，直到树中所有结点都出队， 出队结点的先后顺序就是层次遍历的最终结果

代码

  1. // 二叉树
  3. package main
  5. import "fmt"
  7. type Hero struct {
  8.     No    int
  9.     Name  string
  10.     Left  *Hero // 指向左边节点的指针
  11.     Right *Hero // 指向右边节点的指针
  12. }
  14. // 前序遍历 - 先输出根节点，然后输出左子树，最后输出右子树
  15. func PreOrder(node *Hero) {
  16.     if node != nil {
  17.         // 递归调用，先根再左后右
  18.         fmt.Printf("No=%v, Name=%v \n", node.No, node.Name)
  19.         PreOrder(node.Left)
  20.         PreOrder(node.Right)
  21.     }
  22. }
  24. // 中序遍历 - 先输出左子树，然后输出根节点，最后输出右子树
  25. func InfixOrder(node *Hero) {
  26.     if node != nil {
  27.         // 递归调用，先左再根后右
  28.         InfixOrder(node.Left)
  29.         fmt.Printf("No=%v, Name=%v \n", node.No, node.Name)
  30.         InfixOrder(node.Right)
  31.     }
  32. }
  34. // 后序遍历 - 先输出左子树，然后输出右子树，最后输出根节点
  35. func PostOrder(node *Hero) {
  36.     if node != nil {
  37.         // 递归调用，先左再右后根
  38.         PostOrder(node.Left)
  39.         PostOrder(node.Right)
  40.         fmt.Printf("No=%v, Name=%v \n", node.No, node.Name)
  41.     }
  42. }
  44. /*
  45. 层序遍历：
  46. 借助队列先进先出的特性，从树的根结点开始，依次将其左子节点和右子节点入队。
  47. 而后每次队列中一个结点出队，都将其左子节点和右子节点入队，直到树中所有结点都出队，
  48. 出队结点的先后顺序就是层次遍历的最终结果
  49. */
  50. func levelOrder(node *Hero) [][]int {
  51.     ret := [][]int{} // 定义一个存放遍历之后的数组
  52.     fmt.Printf("res类型： %T \n", ret)
  53.     if node == nil {
  54.         return ret
  55.     }
  56.     q := []*Hero{node} // 将整颗树怼进队列里
  57.     for i := 0; len(q) > 0; i++ {
  58.         ret = append(ret, []int{})
  59.         p := []*Hero{}
  60.         for j := 0; j < len(q); j++ {
  61.             node := q[j]
  62.             ret[i] = append(ret[i], node.No)
  63.             if node.Left != nil {
  64.                 p = append(p, node.Left)
  65.             }
  66.             if node.Right != nil {
  67.                 p = append(p, node.Right)
  68.             }
  69.         }
  70.         q = p
  71.     }
  72.     return ret
  73. }
  75. func main() {
  76.     // 构建二叉树
  77.     root := &Hero{
  78.         No:   1,
  79.         Name: "xixi",
  80.     }
  81.     left1 := &Hero{
  82.         No:   2,
  83.         Name: "haha",
  84.     }
  85.     left2 := &Hero{
  86.         No:   10,
  87.         Name: "1010",
  88.     }
  89.     right02 := &Hero{
  90.         No:   11,
  91.         Name: "1111",
  92.     }
  93.     right1 := &Hero{
  94.         No:   3,
  95.         Name: "hehe",
  96.     }
  97.     right2 := &Hero{
  98.         No:   4,
  99.         Name: "heihei",
  100.     }
  101.     right5 := &Hero{
  102.         No:   5,
  103.         Name: "5555",
  104.     }
  105.     root.Left = left1
  106.     root.Right = right1
  107.     right1.Right = right2
  109.     left1.Left = left2
  110.     left1.Right = right02
  112.     right1.Left = right5
  114.     fmt.Println("前序遍历---")
  115.     // 前序遍历
  116.     PreOrder(root)
  118.     fmt.Println("中序遍历---")
  119.     // 中序遍历
  120.     InfixOrder(root)
  122.     // 后续遍历
  123.     fmt.Println("后续遍历---")
  124.     PostOrder(root)
  126.     fmt.Println("层序遍历---")
  127.     arr := levelOrder(root)
  128.     fmt.Println("arr = ", arr)
  129. }
  131. // 前序遍历
  132. /*
  133. No=1, Name=xixi
  134. No=2, Name=haha
  135. No=10, Name=1010
  136. No=11, Name=1111
  137. No=3, Name=hehe
  138. No=5, Name=5555
  139. No=4, Name=heihei
  140. */
  142. // 中序遍历
  143. /*
  144. No=10, Name=1010
  145. No=2, Name=haha
  146. No=11, Name=1111
  147. No=1, Name=xixi
  148. No=5, Name=5555
  149. No=3, Name=hehe
  150. No=4, Name=heihei
  151. */
  153. // 后序遍历
  154. /*
  155.  No=10, Name=1010
  156. No=11, Name=1111
  157. No=2, Name=haha
  158. No=5, Name=5555
  159. No=4, Name=heihei
  160. No=3, Name=hehe
  161. No=1, Name=xixi
  162. */
  164. // 层序遍历---
  165. /* res类型： [][]int
  166. arr =  [[1] [2 3] [10 11 5 4]] */