目录

• 二叉树介绍
• 广度优先遍历
  • 创建二叉树
  • 广度遍历
• 深度优先遍历
  • 先、中、后序遍历
  • 利用函数编程得到节点总数
  • 利用channel得到最大节点值

介绍

树的遍历是树的一种重要的运算。树的两种重要的遍历模式是深度优先遍历和广度优先遍历，深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

广度优先遍历

通过查看左孩子和右孩子是否为空的条件下，来从左到右的广度的遍历。

• 创建二叉树

import "fmt"
//struct：结构体
type Node struct {
    Value int
    Left,Right *Node
}

//工厂方法,一般返回结构的地址
//局部变量：一般分配在栈上的，如果在传出则需要在堆上分派，go自动规划
func CreateNode(value int) *Node  {
    return &Node{Value: value}
}

//等同一起func print(node Node) {
//代码该方法是由Node使用
func (node Node) Print() {
    fmt.Print(node.Value , " ")
}

//go函数都是传值
//要解决Node中value在main中使用，用指定
func (node *Node) SetValue(value int) {
    node.Value = value
}

• 广度遍历

type Queue[] Node
func (q *Queue) Push(v Node)  {
    *q = append(*q,v)
}
func (q *Queue) Pop() Node  {
    head := (*q)[0]
    *q = (*q)[1:]
    return head
}

func (q *Queue) IsEmpty() bool{
    return len(*q) ==0
}

//宽度遍历
func (node *Node) BreathTraverse(){
    if node == nil  {
        return
    }

    queue := Queue{Node{node.Value,node.Left,node.Right}}
    for len(queue)>0 {
        cur:= queue[0]
        queue = queue[1:]

        cur.Print()
        if cur.Left != nil {
            node1 := Node{cur.Left.Value,cur.Left.Left,cur.Left.Right}
            queue.Push(node1)
        }
        if cur.Right != nil {
            node1 := Node{cur.Right.Value,cur.Right.Left,cur.Right.Right}
            queue.Push(node1)
        }
    }
}

深度优先遍历

对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别：

• 先序遍历（preorder）
• 中序遍历（inorder）
• 后序遍历（postorder）

//前序遍历: 根在前，从左往右
func (node *Node) PreOrder() {
    if node == nil {
        return
    }
    node.Print()
    node.Left.PreOrder()
    node.Right.PreOrder()
}

//中序遍历: 根在中，从左往右
func (node *Node) InOrder() {
    if node == nil {
        return
    }
    node.Left.InOrder()
    node.Print()
    node.Right.InOrder()
}



//后序遍历: 根在前，从下左往下右
func (node *Node) PostOrder() {
    if node == nil {
        return
    }
    node.Right.PostOrder()
    node.Print()
    node.Left.PostOrder()
}

• 利用函数编程得到节点总数

//遍历二叉树
func  (node *Node) traverseFunc(f func(n *Node)){
    if node == nil {
        return
    }
    node.Left.traverseFunc(f)
    f(node)
    node.Right.traverseFunc(f)
}
//得到个数
func (node *Node) Count() int {
    var icount int
    node.traverseFunc(func(nn *Node) {
        icount ++
    })
    return icount
}

• 利用channel得到最大节点值

//遍历二叉树
func  (node *Node) TraverseWithChannel() chan *Node{
    out := make(chan *Node)
    go func() {
        node.traverseFunc(func(node *Node) {
            out <- node
        })
        close(out)
    }()
    return out
}

//得到最大节点的数值
func  (node *Node) getMaxNodeValue() int{
    c := node.TraverseWithChannel()
    maxNode :=0
    for node := range c{
        if node.Value>maxNode {
            maxNode = node.Value
        }
    }
    return maxNode
}