算法—二叉树递归遍历_中序遍历二叉树递归算法的完整代码

测试的二叉树的结构

		root
lfb1 			rtb1
						rtb2                                           
1
2
3

控制台输出的遍历结果

======从根节点开始,前序遍历此二叉树=======
root
lfb1
rtb1
rtb2
======从根节点开始,中序遍历此二叉树=======
lfb1
root
rtb1
rtb2
======从根节点开始,后续遍历此二叉树=======
lfb1
rtb2
rtb1
root

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

源码
使用递归的方式实现三种遍历。所谓递归，简单地讲，就是某个方法调用本身（但必须设置递归结束的条件，否则方法一直进行压栈操作，栈内存瞬间崩溃）

package datastructure;

import java.util.ArrayList;

/**
 * 实现二叉树的前序、中序、后续遍历
 * @Author gzx
 * @create 2022-1-26
 */
public class BinaryTree {
	public static void main(String[] args) {
//		1.构造节点，并设置节点之间的关系
		Node<String> root = new Node<>();
		root.setData("root");
		Node<String> lfb1 = new Node<>();
		lfb1.setData("lfb1");
		root.setLf(lfb1);
		Node<String> rtb1 = new Node<>();
		rtb1.setData("rtb1");
		root.setRt(rtb1);
		Node<String> rtb2=new Node<>();
		rtb2.setData("rtb2");
		rtb1.setRt(rtb2);
//		2.使用上述节点构造二叉树
		BinaryTree binaryTree = new BinaryTree();
		binaryTree.add(root);
		binaryTree.add(lfb1);
		binaryTree.add(rtb1);
		binaryTree.add(rtb2);
//		3分别使用.前序、中序、后续遍历此二叉树
		System.out.println("======从根节点开始,前序遍历此二叉树=======");
		binaryTree.preErgodic(root);
		System.out.println("======从根节点开始,中序遍历此二叉树=======");
		binaryTree.midErgodic(root);
		System.out.println("======从根节点开始,后续遍历此二叉树=======");
		binaryTree.posErgodic(root);
	}

	private ArrayList<Node<?>> tree = null;

	public synchronized void add(Node<?> node) {
		if (null == tree) {
			tree = new ArrayList<>();
		}
		tree.add(node);
	}

	public Node<?> getRoot() {
		if (tree != null && tree.size() > 0) {
			return tree.get(0);
		} else {
			return null;
		}
	}

	/**
	 * @param root 从指定节点开始前序遍历
	 */
	public void preErgodic(Node<?> root) {
		if (root == null)
			return;
		System.out.println(root.getData());
		if (root.getLf() != null)
			preErgodic(root.getLf());
		if (root.getRt() != null)
			preErgodic(root.getRt());
	}

	/**
	 * @param root 从指定节点开始中序遍历
	 */
	public void midErgodic(Node<?> root) {
		if (null == root)
			return;
		if (root.getLf() != null)
			midErgodic(root.getLf());
		System.out.println(root.getData());
		if (root.getRt() != null)
			midErgodic(root.getRt());
	}

	/**
	 * @param root 从指定节点开始后序遍历
	 */
	public void posErgodic(Node<?> root) {
		if (null == root)
			return;
		if (root.getLf() != null)
			posErgodic(root.getLf());
		if (root.getRt() != null)
			posErgodic(root.getRt());
		System.out.println(root.getData());
	}

}

/**
 * 该类的一个实例表示二叉树中的一个节点<br>
 * 此类维护了三个Node类型的引用（pt,lf,rt），内存开销较大<br> 
 * V 当前节点的数据的类型
 */
class Node<V> {
	/** left node */
	private Node<?> lf = null;
	/** parent node */
	private Node<?> pt = null;
	/** right node */
	private Node<?> rt = null;
	/** current node's value */
	private V data;

	public Node() {
	}

	public Node(Node<?> lf, Node<?> pt, V data) {
		this.setLf(lf);
		this.setRt(rt);
		this.data = data;
	}

	public Node<?> getLf() {
		return lf;
	}

	public Node<?> getPt() {
		return pt;
	}

	public Node<?> getRt() {
		return rt;
	}

	public V getData() {
		return data;
	}

	/**
	 * 设置指定节点lf为当前节点的左节点<br>
	 *然后将当前节点设置为指定节点的父节点
	 */
	public void setLf(Node<?> lf) {
		this.lf = lf;
		lf.setPt(this);
	}

	private void setPt(Node<?> pt) {
		this.pt = pt;
	}
	/**
	 *设置指定节点rt为当前节点的右节点<br>
	 *然后将当前节点设置为rt节点的父节点
	 */

	public void setRt(Node<?> rt) {
		this.rt = rt;
		rt.setPt(this);
	}

	public void setData(V data) {
		this.data = data;
	}
	/*-------下列方法用于判断当前节点的类型，但遍历时并未用到----------*/
	/**
	 * @return true if this node is root,false otherwise
	 */
	public boolean isRoot() {
		return this.getPt() == null;
	}

	/**
	 * @return true if this node is branch,false otherwise
	 */
	public boolean isBranch() {
		return this.getPt() != null && (this.getLf() != null || this.getRt() != null);
	}

	/**
	 * @return true if this node is leaf,false otherwise
	 */
	public boolean isLeaf() {
		return this.getPt() != null && this.getLf() == null && this.getRt() == null;
	}

	/**
	 * @return true if this node is left leaf node or is the only node in the b
	 *         tree,false otherwise
	 */
	public boolean isLeftLeaf() {
		return (this.isLeaf() && this.getPt().getLf() == this) || (this.isRoot() && this.isLeaf()/* 仅有一个节点 */);
	}

	/**
	 * @return true if this node is right leaf node or is the only node in the b
	 *         tree,false otherwise
	 */
	public boolean isRightLeaf() {
		return (this.isLeaf() && this.getPt().getRt() == this) || (this.isRoot() && this.isLeaf()/* 仅有一个节点 */);
	}

	/**
	 * @param bro this node's brother node
	 * @return true if the specified node bro is the brother node of the current
	 *         node(this node),false otherwise
	 */
	public boolean isBrother(Node<?> bro) {
		return this.getPt() != null && this.getPt().getRt() == bro;
	}
}
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208

温馨提示：如读完此篇博客感觉有收获，不妨再看看我的其它博客，皆为原创，且都是自己思考的产物。如有不足之处，也敬请批评指正