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

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

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

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

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）、层次遍历

admin 1年前

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

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

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

admin 官方 1年前

zhou 2年前

zhou 2年前

zhou 2年前

zhou 2年前

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

admin 1年前