算法59-二叉树前中后遍历-栈_先序遍历栈的具体变化

前面学习了二叉树三中遍历，使用递归的方法，现在再来看不适用递归，如何实现三中顺序的遍历

最适合的工具就是栈，通过控制何时栈压入，何时弹出，实现打印

分析：

1、先序遍历：弹出打印;有左孩子-压栈；有右孩子-压栈

2 中序遍历，实际是将一棵树，用左边界分解

• 箭头方向也是压入栈的顺序，
• 子树上永远是处理完所有左子树，再处理根节点，再处理右子树
  

3 后序遍历，与前序遍历相反，先压左，再压右，弹出的数放入另一个栈，最终从另一个栈输出，这样就实现了逆序

代码：

package main

import (
    "fmt"
    "errors"
)

type TreeNode struct {
	Data Data
    // 左子树指针
    left *TreeNode
    // 右子树指针
    right *TreeNode
}

type Data struct{
	Name string
    Age int
    Score float32
}
type Stack []TreeNode

// 入栈
func (s *Stack) push(a *TreeNode) {
	*s = append(*s, *a)
}

// 出栈
func (s *Stack) pop() (TreeNode, error) {
	if (len(*s) == 0) {
        var tree TreeNode
		return tree, errors.New("Empty Stack")
	}
	a := *s
	defer func() {
		*s = a[:len(a) - 1]
	}()
	return a[len(a) - 1], nil
}

//1、先序遍历：弹出打印;有左孩子-压栈；有右孩子-压栈
func PreOrder1(tree *TreeNode) {
    var s Stack = make([]TreeNode,0)

    s.push(tree)
    for len(s)!=0{
        tmp,_:=s.pop()
        // 先打印根节点，当前tree就是根，直接打印
        fmt.Println(tmp.Data.Name)
        // 再打印左子树
        //注意是把弹出来的节点的子树压入
        if tmp.right !=nil{
            s.push(tmp.right)
        }
        if tmp.left !=nil{
            s.push(tmp.left)
        }
    }

}
//2
//从根节点开始一次压入左边界，到边界后触发tree=nil返回，弹出最后压入的数
//令循环因子等于弹出的节点的右子树，同样会触发tree=nil返回，弹出父节点，把父节点的右树压入
//这样利用叶子节点两个nil的子树，弹出了叶子节点以及它的父节点，再把父节点的右树压入
func MidOrder1(tree *TreeNode) {
    var s Stack = make([]TreeNode,0)
    for len(s)!=0 || tree != nil {
        if tree !=nil{
            s.push(tree)
            tree=tree.left
            // fmt.Println(s)
        }else{//到叶子节点，左节点为空，右节点为空，两次弹出，第二次弹出叶子节点的父节点，将循环因子赋给父节点的右节点
            tmp,_:=s.pop()
            fmt.Println(tmp.Data.Name)
            tree=tmp.right
        }
    }
}
//3
//与前序遍历相反，先压左，再压右
//弹出的数先不打印，放在另一个栈，最后从另一个栈弹出就是后序遍历
func PostOrder1(tree *TreeNode) {
    var s Stack = make([]TreeNode,0)
    var s1 Stack = make([]TreeNode,0)
    s.push(tree)
    for len(s)!=0{
        tmp,_:=s.pop()
        // 先打印根节点，当前tree就是根，直接打印
        s1.push(&tmp)
        // 再打印左子树
        //注意是把弹出来的节点的子树压入
        if tmp.left !=nil{
            s.push(tmp.left)
        }
        if tmp.right !=nil{
            s.push(tmp.right)
        }

    }
    for len(s1)!=0{
        tmp,_:=s1.pop()
        fmt.Println(tmp.Data.Name)
    }
}

func main() {
    // 根节点
    var student Data
    student.Name = "root"
    student.Age = 10
    student.Score = 90
	var root TreeNode
	root.Data=student

    
    // 一级左子树
	var student1l Data
    student1l.Name = "left1"
    student1l.Age = 20
    student1l.Score = 80
	var left1 TreeNode
	left1.Data=student1l
    root.left = &left1
    
    // 一级右子树
	var student1r Data

    student1r.Name = "right1"
    student1r.Age = 30
    student1r.Score = 70
	var right1 TreeNode
	right1.Data=student1r

    root.right = &right1
    
    // 二级左子树
    var left2 TreeNode
	var student2l Data

    student2l.Name = "left2"
    student2l.Age = 40
    student2l.Score = 60
    left2.Data=student2l
    left1.left = &left2

	// 三级右子树
	var left3 TreeNode
	var student3l Data

    student3l.Name = "left3"
    student3l.Age = 45
    student3l.Score = 65
    left3.Data=student3l
    left1.right = &left3

	//四级右子树
	var left4 TreeNode
	var student4l Data

    student4l.Name = "left4"
    student4l.Age = 46
    student4l.Score = 66
    left4.Data=student4l
    left3.right = &left4

	//五级右子树
	var left5 TreeNode
	var student5l Data

	student5l.Name = "left5"
	student5l.Age = 47
	student5l.Score = 67
	left5.Data=student5l
	left4.right = &left5
    
    // 调用前序遍历函数
    // PreOrder(&root)
	// MidOrder(&root)
	// PostOrder1(&root)
    // s.push(&root)
    // PreOrder1(&root)
    MidOrder1(&root)
}

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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184