JAVA 26天

JAVA 26天

等价转换思想：如果将前序的左右子树互换, 就可得到中右左; 再进行逆序, 可以得到 左右中. 因此, 要把前序的代码改为后序, 需要首先将 leftChild 和 rightChild 互换, 然后用一个栈来存储需要输出的字符, 最终反向输出即可.

先序

与中序只有输出的位置不同

	
	public void preOrderVisitWithStack() {
		ObjectStack tempStack = new ObjectStack();
		BinaryCharTree tempBinaryCharTree = this;
		while (!tempStack.isEmpty() || tempBinaryCharTree != null) {
			if (tempBinaryCharTree != null) {
				System.out.print("" + tempBinaryCharTree.value + " ");
				tempStack.push(tempBinaryCharTree);
				tempBinaryCharTree = tempBinaryCharTree.leftChild;
			}// Of if
			else {
				tempBinaryCharTree = (BinaryCharTree) tempStack.pop();
				tempBinaryCharTree = tempBinaryCharTree.rightChild;
			}// Of else
		}// Of while
	}// Of preOrderVisitWithStack

后序

以中右左的顺序存储到栈中，最后再从栈中取出即后序遍历。

一个栈在遍历二叉树的时候在随时存取，所以需要另一个栈来存储中右左顺序遍历的结点

	
	public void postOrderVisitWithStack() {
		ObjectStack tempStack = new ObjectStack();
		BinaryCharTree tempNodes = this;
		ObjectStack tempOutPut = new ObjectStack();
		
		while (!tempStack.isEmpty() || tempNodes != null) {
			if (tempNodes != null) {
				tempOutPut.push(tempNodes.value);
				tempStack.push(tempNodes);
				tempNodes = tempNodes.rightChild;
			}// Of if
			else {
				tempNodes = (BinaryCharTree) tempStack.pop();
				tempNodes = tempNodes.leftChild;
			}// Of else
		}// Of while
		
		while (!tempOutPut.isEmpty()) {
			System.out.print("" + tempOutPut.pop() + " ");
		}// Of while
	}// Of postOrderVisitWithStack