【轻知识】Go语言学习：二叉树、BFS、DFS、反转二叉树（BFS、DFS）、层次遍历

我是为了练习方便，先在纸上花了一个二叉搜索树（满的二叉树）。

反转二叉树效果如下：

dfs，讲真看过《大话数据结构》都记住了。当然这不是死记硬背的。而是去理解。

二叉搜索树的中序遍历就是1，2，3，4，5，6，7。

package main

import (
    "fmt"
)

type Tree struct {
    Data int 
    LeftNode *Tree
    RightNode *Tree
}
func createTree()*Tree {
    var root *Tree = &Tree{4,nil,nil}
    root.LeftNode = &Tree{2, nil, nil}
    root.LeftNode.LeftNode = &Tree{1, nil, nil}
    root.LeftNode.RightNode = &Tree{3, nil, nil}
    root.RightNode = &Tree{6, nil, nil}
    root.RightNode.LeftNode = &Tree{5, nil, nil}
    root.RightNode.RightNode = &Tree{7, nil, nil}
    return root
}
func preOrderTraverseTree(root *Tree) {
    if root == nil {
        return 
    }
    fmt.Println(root.Data)
    preOrderTraverseTree(root.LeftNode)
    preOrderTraverseTree(root.RightNode)
}
func inOrderTraverseTree(root *Tree) {
    if root == nil {
        return 
    }
    
    inOrderTraverseTree(root.LeftNode)
    fmt.Println(root.Data)
    inOrderTraverseTree(root.RightNode)
}
func postOrderTraverseTree(root *Tree) {
    if root == nil {
        return 
    }
    postOrderTraverseTree(root.LeftNode)
    postOrderTraverseTree(root.RightNode)
    fmt.Println(root.Data)
}
func bfs(root *Tree) {
    if root == nil {
        return 
    }
    // for root 需要借助队列
    var queue []*Tree
    queue = append(queue, root) 
    for len(queue) > 0 {
        node := queue[0]
        fmt.Println(node.Data)
        if node.LeftNode != nil {
            queue = append(queue, node.LeftNode)
        }
        if node.RightNode != nil {
            queue = append(queue, node.RightNode)
        }
        queue = queue[1:] // 通过这样的方式达到出队列
    }
}
func dfsInverseTree(root *Tree) {
    if root == nil {
        return 
    }
    // 交换左右子树
    tempNode := root.LeftNode
    root.LeftNode = root.RightNode
    root.RightNode = tempNode
    dfsInverseTree(root.LeftNode)
    // fmt.Println(root.Data)
    dfsInverseTree(root.RightNode)                                                                  
}

func bfsInverseTree(root *Tree) {
    if root == nil {
        return 
    }
    // for root 需要借助队列
    var queue []*Tree
    queue = append(queue, root) 
    for len(queue) > 0 {
        node := queue[0]
        // fmt.Println(node.Data)
        // 交换左右子树
        tempNode := node.LeftNode
        node.LeftNode = node.RightNode
        node.RightNode = tempNode
        if node.LeftNode != nil {
            queue = append(queue, node.LeftNode)
        }
        if node.RightNode != nil {
            queue = append(queue, node.RightNode)
        }
        queue = queue[1:] // 通过这样的方式达到出队列
    }
}

func main() {
    root := createTree()
    fmt.Println("pre-------")
    preOrderTraverseTree(root)
    fmt.Println("in-------")
    inOrderTraverseTree(root)
    fmt.Println("post------")
    postOrderTraverseTree(root)
    fmt.Println("bfs------")
    bfs(root)
    fmt.Println("defInverseTree-----")
    dfsInverseTree(root)
    fmt.Println("inorder-----")
    inOrderTraverseTree(root)
    fmt.Println("bfsInverseTree------")
    bfsInverseTree(root)
    fmt.Println("inorder---------")
    inOrderTraverseTree(root)
}

层次遍历

func levelTraverseTree(root *Tree) [][]*Tree {
    if root == nil {
        return [][]*Tree{}
    }
    var arr[][]*Tree
    var oneArr[]*Tree
    var tempArr[]*Tree
    oneArr = append(oneArr,root)
    arr = append(arr, oneArr)
    for i:=0;i<len(oneArr);{
        node := oneArr[i]
        if node.LeftNode != nil {
            tempArr = append(tempArr, node.LeftNode)
        }
        if node.RightNode !=nil {
            tempArr = append(tempArr, node.RightNode)
        }
        if (i == len(oneArr)-1 && len(tempArr)>0) {
            oneArr = tempArr
            arr = append(arr, tempArr)
            tempArr = []*Tree{} 
            i =0
            continue
        }
        i++ 
    }
    return arr
}

然后我们打印下

func main() {
    root := createTree()
    arr := levelTraverseTree(root)
    l := len(arr)
    for i:= 0; i<l; i++ {
        l2 := len(arr[i])
        fmt.Print("[")
        for j:=0;j<l2;j++ {
            fmt.Print(arr[i][j].Data)
        }
        fmt.Print("]\n")
    }
}   

效果如下

[4]
[26]
[1357]

参考资料：

• 《大话数据结构》
• 《数据结构与算法之美》极客专栏
• 《算法面试通关40讲》极客专栏