• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

二叉树遍历

golang 9次浏览

以前在数据结构的书上学过二叉树的遍历,老师讲了前序、中序、后序遍历三种,但是只是讲了一下概念,在纸上画一下遍历的过程,并没有讲代码的实现。
<!–more–>

算法思想

先序遍历

前序遍历的顺序是 根节点-左子树-右子树 。意思是从根节点开始,要一直访问左子树,直到没有左孩子,然后访问右子树。


(图片来自知乎)

理解起来应该是很简单的,不过实现起来就不一样了,图中演示的是用递归的方式遍历的,事实上还可以用迭代来实现,也就是 DFS 和 BFS。

中序遍历

后序遍历

在这个算法演示 的网站上没有找到后序遍历的图,后序遍历的过程就是 左子树-右子树-根节点。

定义树的结构,以下使用的是 golang

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

DFS实现

在遍历二叉树之前先要生成一棵二叉树,可以看到,生成二叉树的过程也是递归的,并且类似这样的代码在很多与二叉树有关的地方都能用到,也可以叫做模板。

递归生成二叉树

package main

import "fmt"

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func main() {
    root := &TreeNode{}
    dfs(root, 1)
    fmt.Println(root.Left)

}

func dfs(p *TreeNode, depth int) {
    if depth < 3 {
        left := &TreeNode{Val: 2 * depth}
        right := &TreeNode{Val: 4 * depth}
        p.Left = left
        p.Right = right
        dfs(p.Left, depth+1)
        dfs(p.Right, depth+1)
    }
}

接下来才是遍历二叉树

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        *res = append(*res, p.Val)
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
    }
}

先访问左孩子节点,再访问右孩子节点,这就是先序遍历了。看一下打印出来的结果

$ go run main.go
[0 2 4 8 4 4 8]

注意,golang 在root 初始化的时候会默认给 root 赋值,Val 的类型为 int ,因此初值为 0。对比一下二叉树和打印出来的节点,是符合 根节点-左子树-右子树 这个过程的。

关于后序遍历和中序遍历的递归实现其实是一样的,只是把递归的顺序变换了一下而已。

中序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        *res = append(*res, p.Val)
        dfsbr(p.Right, res)
    }
}

后序遍历

func dfsbr(p *TreeNode, res *[]int) {
    if p != nil {
        dfsbr(p.Left, res)
        dfsbr(p.Right, res)
        *res = append(*res, p.Val)
    }
}

BFS实现

在 DFS 中,是使用的递归的方式查找,程序运行过程中的数据会保存在系统栈里。而使用 BFS 需要自己创建一个队列,保存程序运行中途的信息。

层序遍历

func bfs(p *TreeNode) []int {
    res := make([]int, 0)
    if p == nil {
        return res
    }
    queue := []*TreeNode{p}
    for len(queue) > 0 {
        length := len(queue)
        for length > 0 {
            length--
            if queue[0].Left != nil {
                queue = append(queue, queue[0].Left)
            }
            if queue[0].Right != nil {
                queue = append(queue, queue[0].Right)
            }
            res = append(res, queue[0].Val)
            queue = queue[1:]
        }
    }
    return res
}

打印结果

$ go run main.go 
[0 2 4 4 8 4 8]

可以看到,层序遍历的结果和上图中画出来的二叉树是一一对应的。

先序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func preorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)

    for len(queue) > 0 || root != nil {
        for root != nil {
            result = append(result, root.Val)
            queue = append(queue, root)
            root = root.Left
        }
        root = queue[len(queue) - 1].Right
        queue = queue[:len(queue) - 1]
    }
    return result
}

中序遍历

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func inorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)
    
    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    
    for len(queue) > 0 || root != nil {
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }

        node := queue[len(queue) - 1]
        queue = queue[:len(queue) - 1]
        result = append(result, node.Val)
        root = node.Right
    }
    return result
}

后序遍历

func postorderTraversal(root *TreeNode) []int {
    result := make([]int, 0)

    if root == nil {
        return result
    }

    queue := make([]*TreeNode, 0)
    var lastVisited *TreeNode

    for len(queue) > 0 || root != nil{
        for root != nil {
            queue = append(queue, root)
            root = root.Left
        }
        n := queue[len(queue) - 1]    
        if n.Right == nil || n.Right == lastVisited {
            result = append(result, n.Val)
            queue = queue[:len(queue) - 1]
            lastVisited = n
        } else {
            root = n.Right
        }
    }

    return result
}

公众号:没有梦想的阿巧 后台回复 “群聊”,一起学习,一起进步


版权声明:本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。
喜欢 (0)