0%

《数据结构与算法》二叉树遍历

二叉树的遍历有多种方式:

  1. 前序遍历
  2. 中序遍历
  3. 后序遍历
  4. 层次遍历

本文只关注非递归的方式,直接看例子

遍历下面这棵树:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
package main

import "fmt"

type Node struct {
val string
left *Node
right *Node
}

func main() {
root := Node{
val: "1",
left: &Node{
val: "2",
left: &Node{
val: "3",
left: nil,
right: nil,
},
right: nil,
},
right: &Node{
val: "4",
left: &Node{
val: "5",
left: nil,
right: nil,
},
right: &Node{
val: "6",
left: nil,
right: &Node{
val: "7",
left: nil,
right: nil,
},
},
},
}
preOrderWalk(&root, func(val string) { // 前序遍历,输出 1234567
fmt.Printf("%s", val)
})
inOrderWalk(&root, func(val string) { // 中序遍历,输出 3215467
fmt.Printf("%s", val)
})
postOrderWalk(&root, func(val string) { // 后序遍历,输出 1467523
fmt.Printf("%s", val)
})
levelWalk(&root, func(val string) { // 层次遍历,输出 1243567
fmt.Printf("%s", val)
})
}

func preOrderWalk(root *Node, cb func(val string)) {
stack := []*Node{}
temp := root
for temp != nil || len(stack) != 0 {
if temp != nil {
stack = append(stack, temp)
cb(temp.val)
temp = temp.left
} else {
pop := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
temp = pop.right
}
}
}

func inOrderWalk(root *Node, cb func(val string)) {
stack := []*Node{}
temp := root
for temp != nil || len(stack) != 0 {
if temp != nil {
stack = append(stack, temp)
temp = temp.left
} else {
pop := stack[len(stack) - 1]
cb(pop.val)
stack = stack[:len(stack) - 1]
temp = pop.right
}
}
}

func postOrderWalk(root *Node, cb func(val string)) {
stack := []*Node{}
temp := root
for temp != nil || len(stack) != 0 {
if temp != nil {
stack = append(stack, temp)
cb(temp.val)
temp = temp.right
} else {
pop := stack[len(stack) - 1]
stack = stack[:len(stack) - 1]
temp = pop.left
}
}
}

func levelWalk(root *Node, cb func(val string)) {
quene := []*Node{root}
cb(root.val)
for len(quene) != 0 {
ele := quene[len(quene) - 1]
quene = quene[:len(quene) - 1]
if ele.left != nil {
quene = append([]*Node{ele.left}, quene...)
cb(ele.left.val)
}
if ele.right != nil {
quene = append([]*Node{ele.right}, quene...)
cb(ele.right.val)
}
}
}



微信关注我,及时接收最新技术文章