乐趣区

关于golang:二叉树遍历

jiezi

以前在数据结构的书上学过二叉树的遍历，老师讲了前序、中序、后序遍历三种，然而只是讲了一下概念，在纸上画一下遍历的过程，并没有讲代码的实现。
<!–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
}

公众号：没有幻想的阿巧 后盾回复 “ 群聊 ”，一起学习，一起提高

退出移动版