二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。

    image.png
    前序遍历
    基本思想：先访问当前结点，再前序遍历左子树，最后再前序遍历右子树即根—左—右
    图中前序遍历结果是：1，2，4，5，7，8，3，6
    中序遍历
    基本思想：先中序遍历左子树，然后再访问当前结点，最后再中序遍历右子树即左—根—右
    图中中序遍历结果是：4，2，7，8，5，1，3，6
    后序遍历
    基本思想：先后序遍历左子树，然后再后序遍历右子树，最后再访问当前结点即左—右—根
    图中后序遍历结果是：4，8，7，5，2，6，3，1
    层次遍历
    基本思想：从第一层开始，依此遍历每层，直到结束
    图中层次遍历结果是：1，2，3，4，5，6，7，8

    image.png

    1. package main
    3. import "fmt"
    5. //定义二叉树的节点
    6. type Node struct {
    7.     value int
    8.     left  *Node
    9.     right *Node
    10. }
    12. func (node *Node) Print() {
    13.     fmt.Printf("%d ", node.value)
    14. }
    16. //功能：设置节点的值
    17. //参数：节点的值
    18. //返回值：nil
    19. func (node *Node) SetValue(value int) {
    20.     node.value = value
    21. }
    23. //功能：创建节点
    24. //参数：节点的值
    25. //返回值：nil
    26. func CreateNode(value int) *Node {
    27.     return &Node{value, nil, nil}
    28. }
    30. //功能：求树的高度,递归实现
    31. //参数：根节点
    32. //返回值：树的高度，树的高度=Max(左子树高度，右子树高度)+1
    33. func (node *Node) GetTreeHeigh() int {
    34.     if node == nil {
    35.         return 0
    36.     } else {
    37.         lHeigh := node.left.GetTreeHeigh()
    38.         rHeigh := node.right.GetTreeHeigh()
    39.         if lHeigh > rHeigh {
    40.             return lHeigh + 1
    41.         } else {
    42.             return rHeigh + 1
    43.         }
    44.     }
    45. }
    47. //功能：求树的高度,通过遍历实现
    48. func (node *Node) GetTreeHeighByQueue() int {
    49.     if node == nil {
    50.         return 0
    51.     }
    52.     height := 0
    53.     nodes := []*Node{node}
    54.     for len(nodes) > 0 {
    55.         height++
    56.         size := len(nodes) // 每层的节点数
    57.         count := 0
    58.         for count < size { // 保证for循环执行完nodes都是不通层的数据
    59.             count++
    60.             currentNode := nodes[0]
    61.             nodes = nodes[1:]
    62.             if currentNode.left != nil {
    63.                 nodes = append(nodes, currentNode.left)
    64.             }
    65.             if currentNode.right != nil {
    66.                 nodes = append(nodes, currentNode.right)
    67.             }
    68.         }
    69.     }
    70.     return height
    71. }
    73. //前序遍历
    74. func (node *Node) PreOrder() {
    75.     if node == nil {
    76.         return
    77.     }
    78.     node.Print()
    79.     node.left.PreOrder()
    80.     node.right.PreOrder()
    81. }
    83. //中序遍历
    84. func (node *Node) MiddleOrder() {
    85.     if node == nil {
    86.         return
    87.     }
    88.     node.left.PostOrder()
    89.     node.Print()
    90.     node.right.PostOrder()
    91. }
    93. //后序遍历
    94. func (node *Node) PostOrder() {
    95.     if node == nil {
    96.         return
    97.     }
    98.     node.left.PostOrder()
    99.     node.right.PostOrder()
    100.     node.Print()
    101. }
    103. //层次遍历
    104. func (node *Node) BreadthFirstSearch() {
    105.     if node == nil {
    106.         return
    107.     }
    108.     res := []int{}
    109.     nodes := []*Node{node}
    110.     for len(nodes) > 0 {
    111.         currentNode := nodes[0]
    112.         res = append(res, currentNode.value)
    113.         nodes = nodes[1:]
    114.         if currentNode.left != nil {
    115.             nodes = append(nodes, currentNode.left)
    116.         }
    117.         if currentNode.right != nil {
    118.             nodes = append(nodes, currentNode.right)
    119.         }
    120.     }
    121.     for _, v := range res {
    122.         fmt.Print(v, " ")
    123.     }
    124. }
    126. func main() {
    127.     root := CreateNode(0)
    128.     root.left = CreateNode(1)
    129.     root.right = CreateNode(2)
    130.     root.left.right = CreateNode(4)
    131.     root.left.left = CreateNode(3)
    132.     root.left.right.left = CreateNode(7)
    133.     root.right.left = CreateNode(5)
    134.     root.right.right = CreateNode(6)
    136.     fmt.Println(root.GetTreeHeigh())         // 4
    137.     fmt.Println(root.GetTreeHeighByQueue()) // 4
    138.     root.PreOrder() // 0 1 3 4 7 2 5 6
    139.     fmt.Println()
    140.     root.MiddleOrder()  // 3 7 4 1 0 5 6 2
    141.     fmt.Println()
    142.     root.PostOrder()  // 3 7 4 1 5 6 2 0
    143.     fmt.Println()
    144.     root.BreadthFirstSearch()  // 0 1 2 3 4 5 6 7
    145. }