Day 13

• Java 树与二叉树（三）
• 一、二叉树深度遍历的栈实现 (中序)
• • 1. 具有通用性的对象栈
  • 2. 中序遍历
• 二、二叉树深度遍历的栈实现 (前序和后序)

（1）改写栈程序, 里面存放对象.
（2）该程序应该放在 datastructure.stack 包内.
（3）还是依靠强制类型转换, 支持不同的数据类型.
（4）增加了 isEmpty() 方法.
代码如下：

package datastructure.stack;


public class ObjectStack {

	// The depth
	public static final int MAX_DEPTH = 10;

	// The actual depth.
	int depth;

	// The data
	Object[] data;

	
	public ObjectStack() {
		depth = 0;
		data = new Object[MAX_DEPTH];
	}// Of the first constructor

	
	@Override
	public String toString() {
		String resultString = " ";
		for (int i = 0; i < depth; i++) {
			resultString += data[i];
		} // Of for i

		return resultString;
	}// Of toString

	
	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

	
	public Object pop() {
		if (depth == 0) {
			System.out.println("Nothing to pop.");
			return '';
		} // of if

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

		return resultObject;
	}// Of pop

	
	public boolean isEmpty() {
		if (depth == 0) {
			return true;
		} // Of if

		return false;
	}// Of isEmpty

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ObjectStack tempStack = new ObjectStack();

		for (char ch = 'a'; ch < 'm'; ch++) {
			tempStack.push(new Character(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

运行结果：

（1）代码依然短.
（2）中序是几种遍历中最简单的.
（3）具体设计思路自己琢磨, 用几个例子来运行就懂了.
代码如下：

	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

以为前序和后序要比中序难很多, 其实并没有.

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 中潘佳豪的版本.

代码如下：

	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

	
	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(new Character(tempNode.value));
				tempStack.push(tempNode);
				tempNode = tempNode.rightChild;
			} else {
				tempNode = (BinaryCharTree) tempStack.pop();
				tempNode = tempNode.leftChild;
			} // Of if
		} // Of while

		// Now reverse ouput.
		while (!tempOutputStack.isEmpty()) {
			System.out.print("" + tempOutputStack.pop() + " ");
		} // of while
	}// Of postOrderVisitWithStack
	
	public static void main(String args[]) {
		BinaryCharTree tempTree = manualConstructTree();
		System.out.println("rnPreorder visit:");
		tempTree.preOrderVisit();
		System.out.println("rnIn-order visit:");
		tempTree.inOrderVisit();
		System.out.println("rnPost-order visit:");
		tempTree.postOrderVisit();

		System.out.println("rnrnThe depth is: " + tempTree.getDepth());
		System.out.println("The number of nodes is: " + tempTree.getNumNodes());

		tempTree.toDataArrays();
		System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
		System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));

		tempTree.toDataArraysObjectQueue();
		System.out.println("Only object queue.");
		System.out.println("The values are: " + Arrays.toString(tempTree.valuesArray));
		System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));

		char[] tempCharArray = { 'A', 'B', 'C', 'D', 'E', 'F' };
		int[] tempIndicesArray = { 0, 1, 2, 4, 5, 12 };
		BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);

		System.out.println("rnPreorder visit:");
		tempTree2.preOrderVisit();
		System.out.println("rnIn-order visit:");
		tempTree2.inOrderVisit();
		System.out.println("rnPost-order visit:");
		tempTree2.postOrderVisit();

		System.out.println("rnIn-order visit with stack:");
		tempTree2.inOrderVisitWithStack();
		System.out.println("rnPre-order visit with stack:");
		tempTree2.preOrderVisitWithStack();
		System.out.println("rnPost-order visit with stack:");
		tempTree2.postOrderVisitWithStack();

	}// Of main

}// Of class BinaryCharTree

运行结果：