Skip to content

Commit 61e06c9

Browse files
dairongpengdairongpeng
committed
feat: 二叉树的遍历
1 parent d12209c commit 61e06c9

File tree

1 file changed

+98
-79
lines changed

1 file changed

+98
-79
lines changed

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

Lines changed: 98 additions & 79 deletions
Original file line numberDiff line numberDiff line change
@@ -5,15 +5,15 @@
55

66
### 1.1.1 二叉树节点定义
77

8-
```Java
9-
Class Node{
10-
// 节点的值类型
11-
V value;
12-
// 二叉树的左孩子指针
13-
Node left;
14-
// 二叉树的右孩子指针
15-
Node right;
16-
}
8+
```Go
9+
type Node struct {
10+
// 二叉树节点上的值
11+
Val int
12+
// 左孩子
13+
Left *Node
14+
// 右孩子
15+
Right *Node
16+
}
1717
```
1818

1919
### 1.1.2 递归实现先序中序后序遍历
@@ -42,89 +42,108 @@ graph TD
4242

4343
3、 后序遍历为：4 5 2 6 7 3 1
4444

45-
```Java
46-
package class07;
47-
48-
public class Code01_RecursiveTraversalBT {
49-
50-
public static class Node {
51-
public int value;
52-
public Node left;
53-
public Node right;
54-
55-
public Node(int v) {
56-
value = v;
57-
}
58-
}
45+
```Go
46+
package main
5947

60-
public static void f(Node head) {
61-
if (head == null) {
62-
return;
63-
}
64-
// 1 此处打印等于先序
65-
f(head.left);
66-
// 2 此处打印等于中序
67-
f(head.right);
68-
// 3 此处打印等于后序
69-
}
48+
import "fmt"
7049

71-
// 先序打印所有节点
72-
public static void pre(Node head) {
73-
if (head == null) {
74-
return;
75-
}
76-
// 打印头
77-
System.out.println(head.value);
78-
// 递归打印左子树
79-
pre(head.left);
80-
// 递归打印右子树
81-
pre(head.right);
82-
}
50+
type Node struct {
51+
// 二叉树节点上的值
52+
Val int
53+
// 左孩子
54+
Left *Node
55+
// 右孩子
56+
Right *Node
57+
}
8358

84-
// 中序遍历
85-
public static void in(Node head) {
86-
if (head == null) {
87-
return;
88-
}
89-
in(head.left);
90-
System.out.println(head.value);
91-
in(head.right);
59+
// Pre 给定二叉树头节点，先序遍历该二叉树
60+
func (head *Node) Pre() {
61+
if head == nil {
62+
return
9263
}
64+
// 获取头节点，打印该头结点
65+
fmt.Println(head.Val)
66+
// 递归遍历左子树
67+
head.Left.Pre()
68+
// 递归遍历右子树
69+
head.Right.Pre()
70+
}
9371

94-
// 后序遍历
95-
public static void pos(Node head) {
96-
if (head == null) {
97-
return;
98-
}
99-
pos(head.left);
100-
pos(head.right);
101-
System.out.println(head.value);
72+
// Mid 给定二叉树头节点，中序遍历该二叉树
73+
func (head *Node) Mid() {
74+
if head == nil {
75+
return
10276
}
77+
// 递归遍历左子树
78+
head.Left.Mid()
79+
// 获取头节点，打印该头结点
80+
fmt.Println(head.Val)
81+
// 递归遍历右子树
82+
head.Right.Mid()
83+
}
10384

104-
public static void main(String[] args) {
105-
Node head = new Node(1);
106-
head.left = new Node(2);
107-
head.right = new Node(3);
108-
head.left.left = new Node(4);
109-
head.left.right = new Node(5);
110-
head.right.left = new Node(6);
111-
head.right.right = new Node(7);
112-
113-
pre(head);
114-
System.out.println("========");
115-
in(head);
116-
System.out.println("========");
117-
pos(head);
118-
System.out.println("========");
119-
85+
// Pos 给定二叉树头节点，后序遍历该二叉树
86+
func (head *Node) Pos() {
87+
if head == nil {
88+
return
12089
}
90+
// 递归遍历左子树
91+
head.Left.Pos()
92+
// 递归遍历右子树
93+
head.Right.Pos()
94+
// 获取头节点，打印该头结点
95+
fmt.Println(head.Val)
96+
}
12197

98+
func main() {
99+
head := &Node{Val: 1}
100+
head.Left = &Node{Val: 2}
101+
head.Right = &Node{Val: 3}
102+
head.Left.Left = &Node{Val: 4}
103+
head.Left.Right = &Node{Val: 5}
104+
head.Right.Left = &Node{Val: 6}
105+
head.Right.Right = &Node{Val: 7}
106+
107+
head.Pre()
108+
fmt.Println("=========")
109+
head.Mid()
110+
fmt.Println("=========")
111+
head.Pos()
122112
}
123113
```
124114

125-
> 结论：对于树的递归，每个节点实质上会到达三次，例如上文的树结构，对于f函数，我们传入头结点，再调用左树再调用右树。实质上经过的路径为1 2 4 4 4 2 5 5 5 2 1 3 6 6 6 3 7 7 7 3 1。我们在每个节点三次返回的基础上，第一次到达该节点就打印，就是先序，第二次到达该节点打印就是中序，第三次到达该节点就是后序。
115+
输出：
116+
117+
```shell
118+
1
119+
2
120+
4
121+
5
122+
3
123+
6
124+
7
125+
=========
126+
4
127+
2
128+
5
129+
1
130+
6
131+
3
132+
7
133+
=========
134+
4
135+
5
136+
2
137+
6
138+
7
139+
3
140+
1
141+
142+
Process finished with the exit code 0
143+
144+
```
126145

127-
> 所以先序中序后序，只是我们的递归顺序加工出来的结果！
146+
> 总结：对于树的递归，每个节点在递归的过程中实质上会到达三次，例如上文的树结构，我们在第一次到达当前节点就打印，对于以当前节点为树根的树，就是先序。同理，第二次到达当前节点就是中序，第三次到达该节点就是后序遍历。所以先序中序后序，只是我们的递归顺序加工出来的结果而已
128147
129148
### 1.1.3 非递归实现先序中序后序遍历(DFS)
130149

0 commit comments

Comments
 (0)