网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

2020-06-10 02:45:06 admin 804

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

image.png

反转二叉树效果如下：

image.png

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讲》极客专栏

转载文章，原文链接：【轻知识】Go语言学习：二叉树、BFS、DFS、反转二叉树（BFS、DFS）、层次遍历

关键字词二叉树 BFS

分享到：

上一篇：实战Go内存泄露

下一篇：我要在栈上。不，你应该在堆上

如需留言，请登录，没有账号？请注册

0 条评论 0 人参与

网站首页 返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

zhou 3年前

zhou 3年前

zhou 3年前

zhou 3年前

武云 3年前

网站首页 返回列表 像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。

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

zhou 3年前

zhou 3年前

zhou 3年前

zhou 3年前

武云 3年前

网站首页返回列表像“草根”一样，紧贴着地面，低调的存在，冬去春来，枯荣无恙。