Java学习-Day13

二叉树深度遍历的栈实现 (中序)

中序遍历在之前是用递归的方式来实现的, 递归的本质就是栈. 只不过递归使用的是系统提供的栈, 当然我们也可以编写手工栈来实现之前系统栈的功能. 这就是这一节需要完成的任务. 那么第一个任务就是编写一个栈.

一、具有通用性的对象栈

简而言之就是把之前的字符栈转变为适合于所有数据结构的对象栈, 其中方法也和之前的大同小异. 这里新增了判断栈是否为空的代码.

1. 入栈

描述

向栈中添加一个元素.

输入

一个Object类的对象

输出

若栈满则打印 "Stack full." 然后返回 false .

若栈未满则返回 true .

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 *********************
 * Push an element.
 * 
 * @param paraObject The given object.
 * @return Success or not.
 *********************
 */
public boolean push(Object paraObject) {
	if (depth == MAX_DEPTH) {
		System.out.println("Stack full.");
		return false;
	} // Of if

	data[depth] = paraObject;
	depth++;

	return true;
}// Of push

2. 出栈

描述

从栈顶去除一个元素.

输入

无

输出

返回一个类为Object的对象为之前的栈顶元素.

若栈为空则打印 "Nothing to pop." 并返回 '\0' .

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 *********************
 * Pop an element.
 * 
 * @return The object at the top of the stack.
 *********************
 */
public Object pop() {
	if (depth == 0) {
		System.out.println("Nothing to pop.");
		return '\0';
	} // of if

	Object resultObject = data[depth - 1];
	depth--;

	return resultObject;
}// Of pop

3. 栈判空

描述

通过代码中栈指针的位置判断当前栈中是否还有元素.

输入

无

输出

栈中还有元素返回 false .

栈中无元素返回 true .

具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 *********************
 * Is the stack empty?
 * 
 * @return True if empty.
 *********************
 */
public boolean isEmpty() {
	if (depth == 0) {
		return true;
	} // Of if

	return false;
}// Of isEmpty

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
119
120
121
122
123
124
125
package datastructure.stack;

/**
 * Object stack.
 * 
 * @author Shihuai Wen Email:wshysxcc@outlook.com
 */
public class ObjectStack {
	/**
	 * The depth.
	 */
	public static final int MAX_DEPTH = 10;

	/**
	 * The actual depth.
	 */
	int depth;

	/**
	 * The data
	 */
	Object[] data;

	/**
	 *********************
	 * Construct an empty sequential list.
	 *********************
	 */
	public ObjectStack() {
		depth = 0;
		data = new Object[MAX_DEPTH];
	}// Of the first constructor

	/**
	 *********************
	 * Overrides the method claimed in Object, the superclass of any class.
	 *********************
	 */
	@Override
	public String toString() {
		String resultString = "";
		for (int i = 0; i < depth; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	/**
	 *********************
	 * Push an element.
	 * 
	 * @param paraObject The given object.
	 * @return Success or not.
	 *********************
	 */
	public boolean push(Object paraObject) {
		if (depth == MAX_DEPTH) {
			System.out.println("Stack full.");
			return false;
		} // Of if

		data[depth] = paraObject;
		depth++;

		return true;
	}// Of push

	/**
	 *********************
	 * Pop an element.
	 * 
	 * @return The object at the top of the stack.
	 *********************
	 */
	public Object pop() {
		if (depth == 0) {
			System.out.println("Nothing to pop.");
			return '\0';
		} // of if

		Object resultObject = data[depth - 1];
		depth--;

		return resultObject;
	}// Of pop

	/**
	 *********************
	 * Is the stack empty?
	 * 
	 * @return True if empty.
	 *********************
	 */
	public boolean isEmpty() {
		if (depth == 0) {
			return true;
		} // Of if

		return false;
	}// Of isEmpty

	/**
	 *********************
	 * The entrance of the program.
	 * 
	 * @param args Not used now.
	 *********************
	 */
	public static void main(String args[]) {
		ObjectStack tempStack = new ObjectStack();

		for (char ch = 'a'; ch < 'm'; ch++) {
			tempStack.push(Character.valueOf(ch));
			System.out.println("The current stack is: " + tempStack);
		} // Of for i

		char tempChar;
		for (int i = 0; i < 12; i++) {
			tempChar = ((Character) tempStack.pop()).charValue();
			System.out.println("Poped: " + tempChar);
			System.out.println("The current stack is: " + tempStack);
		} // Of for i
	}// Of main
}// Of class ObjectStack

5. 运行截图

二、中序遍历

1. 描述

具体思路来自LeetCode题解.

这里对算法进行简单的介绍.

从根开始入栈, 当一个节点入栈后对该节点的左子节点判断是否为空, 若不为空则入栈. 重复以上步骤直到左子节点为空, 然后开始出栈输出元素. 节点出栈后判断是否有右边子节点, 若不为空则重复之前对左子节点的处理方式.

2. 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 *********************
 * In-order visit with stack.
 *********************
 */
public void inOrderVisitWithStack() {
	ObjectStack tempStack = new ObjectStack();
	BinaryCharTree tempNode = this;
	while (!tempStack.isEmpty() || tempNode != null) {
		if (tempNode != null) {
			tempStack.push(tempNode);
			tempNode = tempNode.leftChild;
		} else {
			tempNode = (BinaryCharTree) tempStack.pop();
			System.out.print("" + tempNode.value + " ");
			tempNode = tempNode.rightChild;
		} // Of if
	} // Of while
}// Of inOrderVisitWithStack

3. 运行截图

二叉树深度遍历的栈实现 (前序和后序)

一、描述

前序和后序无论是哪种在递归中都是使用栈.

  1. 前序、后序与中序的区别, 仅仅在于输出语句的位置不同.

  2. 二叉树的遍历, 总共有 6 种排列: 1) 左中右 (中序); 2) 左右中 (后序); 3) 中左右 (前序); 4) 中右左; 5) 右左中; 6) 右中左. 我们平常关心的是前三种, 是因为我们习惯于先左后右. 如果要先右后左, 就相当于左右子树互换, 这个是很容易做到的.

  3. 如果将前序的左右子树互换, 就可得到 4) 中右左; 再进行逆序, 可以得到 2) 左右中. 因此, 要把前序的代码改为后序, 需要首先将 leftChild 和 rightChild 互换, 然后用一个栈来存储需要输出的字符, 最终反向输出即可. 这种将一个问题转换成另一个等价问题的方式, 无论在数学还是计算机领域, 都极度重要. 参见 https://blog.csdn.net/minfanphd/article/details/117318844 中莫峦奇的版本.

  4. 如果不按上述方式, 直接写后序遍历, 就会复杂得多, 有双重的 while 循环. 参见 https://blog.csdn.net/minfanphd/article/details/117318844 中潘佳豪的版本.

  5. 知乎https://zhuanlan.zhihu.com/p/80578741对以上两种方法进行了更加详细的介绍.

  6. 改变二叉树的数据结构, 在其中添加一个变量用于记录是否入过栈. 这样就可以按照中右左压栈. 判断栈顶是否存在左右子节点, 不存在就出栈. 若存在则判断其子节点是否如果栈, 如果入过则跳过.

二、先序遍历

1. 描述

同之前中序遍历一样, 只不过在入栈之前就把根访问了.

2. 具体代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 *********************
 * Pre-order visit with stack.
 *********************
 */
public void preOrderVisitWithStack() {
	ObjectStack tempStack = new ObjectStack();
	BinaryCharTree tempNode = this;
	while (!tempStack.isEmpty() || tempNode != null) {
		if (tempNode != null) {
			System.out.print("" + tempNode.value + " ");
			tempStack.push(tempNode);
			tempNode = tempNode.leftChild;
		} else {
			tempNode = (BinaryCharTree) tempStack.pop();
			tempNode = tempNode.rightChild;
		} // Of if
	} // Of while
}// Of preOrderVisitWithStack

3. 运行截图

三、后序遍历

1. 描述

可以观察到, 可以先求出遍历顺序是根右左的节点序列, 再倒序，便刚好是后序遍历的顺序: 左右根. 而遍历顺序是根右左的话, 很好办, 从前序遍历的代码中改两行就是了.

所以我们可以选用两个栈, 一个用于根右左遍历, 一个用于保存序列, 最后的代码和前序遍历只是稍作几点修改即可.

2. 具体代码

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
/**
 *********************
 * Post-order visit with stack.
 *********************
 */
public void postOrderVisitWithStack() {
	ObjectStack tempStack = new ObjectStack();
	BinaryCharTree tempNode = this;
	ObjectStack tempOutputStack = new ObjectStack();

	while (!tempStack.isEmpty() || tempNode != null) {
		if (tempNode != null) {
			// Store for output.
			tempOutputStack.push(Character.valueOf(tempNode.value));
			tempStack.push(tempNode);
			tempNode = tempNode.rightChild;
		} else {
			tempNode = (BinaryCharTree) tempStack.pop();
			tempNode = tempNode.leftChild;
		} // Of if
	} // Of while

	// Now reverse output.
	while (!tempOutputStack.isEmpty()) {
		System.out.print("" + tempOutputStack.pop() + " ");
	} // Of while
}// Of postOrderVisitWithStack

3. 运行截图

总结

当我拿到一个问题的时候我首先想到的就是暴力破解, 就算我写的代码很烂, 计算机还是能够给出我答案. 换个角度解决问题其实很值得我学习, 等量代换就是一个很好的例子.

一道题不应该只能被暴力破解.