以前在資料結構的書上學過二叉樹的遍歷，老師講了前序、中序、后序遍歷三種，但是只是講了一下概念，在紙上畫一下遍歷的程序，并沒有講代碼的實作，
演算法思想
先序遍歷
前序遍歷的順序是 根節點-左子樹-右子樹 ，意思是從根節點開始，要一直訪問左子樹，直到沒有左孩子，然后訪問右子樹，
(圖片來自知乎)
理解起來應該是很簡單的，不過實作起來就不一樣了，圖中演示的是用遞回的方式遍歷的，事實上還可以用迭代來實作，也就是 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
}
公眾號：沒有夢想的阿巧 后臺回復 "群聊"，一起學習，一起進步
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/165374.html
標籤：其他