Skip to content

Commit 31c4fc2

Browse files
dairongpengdairongpeng
committed
feat: 二叉树非递归遍历
1 parent 61e06c9 commit 31c4fc2

File tree

1 file changed

+92
-114
lines changed

1 file changed

+92
-114
lines changed

‎07-二叉树基本算法.md

Lines changed: 92 additions & 114 deletions
Original file line numberDiff line numberDiff line change
@@ -147,143 +147,121 @@ Process finished with the exit code 0
147147
148148
### 1.1.3 非递归实现先序中序后序遍历(DFS)
149149

150-
> 思路：由于任何递归可以改为非递归，我们可以使用压栈来实现,实质就是深度优先遍历（DFS）。用先序实现的步骤，其他类似：
150+
思路：由于任何递归可以改为非递归，我们可以使用压栈来实现,实质就是深度优先遍历（DFS）。用先序实现的步骤，其他类似：
151151

152-
> 步骤一，把节点压入栈中，弹出就打印
152+
- 步骤一，把节点压入栈中，弹出就打印
153153

154-
> 步骤二，如果有右孩子先压入右孩子
154+
- 步骤二，如果有右孩子先压入右孩子
155155

156-
> 步骤三，如果有左孩子压入左孩子
156+
- 步骤三，如果有左孩子压入左孩子
157157

158-
```Java
159-
package class07;
160-
161-
import java.util.Stack;
162-
163-
public class Code02_UnRecursiveTraversalBT {
158+
```Go
159+
package main
164160

165-
public static class Node {
166-
public int value;
167-
public Node left;
168-
public Node right;
161+
import "fmt"
169162

170-
public Node(int v) {
171-
value = v;
172-
}
173-
}
163+
type Node struct {
164+
// 二叉树节点上的值
165+
Val int
166+
// 左孩子
167+
Left *Node
168+
// 右孩子
169+
Right *Node
170+
}
174171

175-
// 非递归先序
176-
public static void pre(Node head) {
177-
System.out.print("pre-order: ");
178-
if (head != null) {
179-
Stack<Node> stack = new Stack<Node>();
180-
stack.add(head);
181-
while (!stack.isEmpty()) {
182-
// 弹出就打印
183-
head = stack.pop();
184-
System.out.print(head.value + " ");
185-
// 右孩子不为空，压右
186-
if (head.right != null) {
187-
stack.push(head.right);
188-
}
189-
// 左孩子不为空，压左
190-
if (head.left != null) {
191-
stack.push(head.left);
192-
}
172+
// Pre 给定二叉树头节点，非递归先序遍历该二叉树
173+
func (head *Node) Pre() {
174+
fmt.Println("pre-order: ")
175+
if head != nil {
176+
// 简单模拟一个栈
177+
stack := make([]*Node, 0)
178+
stack = append(stack, head)
179+
for len(stack) != 0 {
180+
// 出栈
181+
hd := stack[len(stack)-1]
182+
fmt.Println(hd.Val)
183+
stack = stack[:len(stack)-1]
184+
// 右孩子入栈
185+
if hd.Right != nil {
186+
stack = append(stack, hd.Right)
187+
}
188+
// 左孩子入栈
189+
if hd.Left != nil {
190+
stack = append(stack, hd.Left)
193191
}
194192
}
195-
System.out.println();
196193
}
194+
fmt.Println()
195+
}
197196

198-
// 非递归中序
199-
public static void in(Node head) {
200-
System.out.print("in-order: ");
201-
if (head != null) {
202-
Stack<Node> stack = new Stack<Node>();
203-
while (!stack.isEmpty() || head != null) {
204-
// 整条左边界依次入栈
205-
if (head != null) {
206-
stack.push(head);
207-
head = head.left;
208-
// 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
209-
} else {
210-
head = stack.pop();
211-
System.out.print(head.value + " ");
212-
head = head.right;
213-
}
197+
// Mid 给定二叉树头节点，非递归中序遍历该二叉树
198+
func (head *Node) Mid() {
199+
fmt.Println("Mid-order:")
200+
if head != nil {
201+
hd := head
202+
// 简单模拟一个栈
203+
stack := make([]*Node, 0)
204+
for len(stack) != 0 || hd != nil {
205+
// 整条左边界依次入栈
206+
if hd != nil {
207+
stack = append(stack, hd)
208+
hd = hd.Left
209+
} else { // 左边界到头弹出一个打印，来到该节点右节点，再把该节点的左树以此进栈
210+
hd = stack[len(stack)-1]
211+
stack = stack[:len(stack)-1]
212+
fmt.Println(hd.Val)
213+
hd = hd.Right
214214
}
215215
}
216-
System.out.println();
217216
}
217+
fmt.Println()
218+
}
218219

219-
// 非递归后序
220-
public static void pos1(Node head) {
221-
System.out.print("pos-order: ");
222-
if (head != null) {
223-
Stack<Node> s1 = new Stack<Node>();
224-
// 辅助栈
225-
Stack<Node> s2 = new Stack<Node>();
226-
s1.push(head);
227-
while (!s1.isEmpty()) {
228-
head = s1.pop();
229-
s2.push(head);
230-
if (head.left != null) {
231-
s1.push(head.left);
232-
}
233-
if (head.right != null) {
234-
s1.push(head.right);
235-
}
220+
// Pos 给定二叉树头节点，非递归后序遍历该二叉树
221+
func (head *Node) Pos() {
222+
fmt.Println("pos-order: ")
223+
if head != nil {
224+
hd := head
225+
// 借助两个辅助栈
226+
s1 := make([]*Node, 0)
227+
s2 := make([]*Node, 0)
228+
s1 = append(s1, hd)
229+
for len(s1) != 0 {
230+
// 出栈
231+
hd = s1[len(s1) - 1]
232+
s1 = s1[:len(s1) - 1]
233+
s2 = append(s2, hd)
234+
if hd.Left != nil {
235+
s1 = append(s1, hd.Left)
236236
}
237-
while (!s2.isEmpty()) {
238-
System.out.print(s2.pop().value + " ");
237+
if hd.Right != nil {
238+
s1 = append(s1, hd.Right)
239239
}
240240
}
241-
System.out.println();
242-
}
243-
244-
// 非递归后序2：用一个栈实现后序遍历，比较有技巧
245-
public static void pos2(Node h) {
246-
System.out.print("pos-order: ");
247-
if (h != null) {
248-
Stack<Node> stack = new Stack<Node>();
249-
stack.push(h);
250-
Node c = null;
251-
while (!stack.isEmpty()) {
252-
c = stack.peek();
253-
if (c.left != null && h != c.left && h != c.right) {
254-
stack.push(c.left);
255-
} else if (c.right != null && h != c.right) {
256-
stack.push(c.right);
257-
} else {
258-
System.out.print(stack.pop().value + " ");
259-
h = c;
260-
}
261-
}
241+
for len(s2) != 0 {
242+
v := s2[len(s2) - 1]
243+
s2 = s2[:len(s2) - 1]
244+
fmt.Println(v.Val)
262245
}
263-
System.out.println();
264246
}
247+
fmt.Println()
248+
}
265249

266-
public static void main(String[] args) {
267-
Node head = new Node(1);
268-
head.left = new Node(2);
269-
head.right = new Node(3);
270-
head.left.left = new Node(4);
271-
head.left.right = new Node(5);
272-
head.right.left = new Node(6);
273-
head.right.right = new Node(7);
274-
275-
pre(head);
276-
System.out.println("========");
277-
in(head);
278-
System.out.println("========");
279-
pos1(head);
280-
System.out.println("========");
281-
pos2(head);
282-
System.out.println("========");
283-
}
250+
func main() {
251+
head := &Node{Val: 1}
252+
head.Left = &Node{Val: 2}
253+
head.Right = &Node{Val: 3}
254+
head.Left.Left = &Node{Val: 4}
255+
head.Left.Right = &Node{Val: 5}
256+
head.Right.Left = &Node{Val: 6}
257+
head.Right.Right = &Node{Val: 7}
284258

259+
head.Pre()
260+
fmt.Println("=========")
261+
head.Mid()
262+
fmt.Println("=========")
263+
head.Pos()
285264
}
286-
287265
```
288266

289267
### 1.1.4 二叉树按层遍历(BFS)

0 commit comments

Comments
 (0)