日撸代码300行：第26天（二叉树深度遍历的栈实现 (前序和后序)）

代码来自闵老师”日撸 Java 三百行（21-30天）“，链接：https://blog.csdn.net/minfanphd/article/details/116975721

	
	public void preOrderVisitWithStack() {
		ObjectStack tempStack = new ObjectStack();
		BinaryCharTree tempNode = this;
		
		while (!tempStack.isEmpty() || tempNode != null) {
			if (tempNode != null) {
				tempStack.push(tempNode);
				System.out.print(" " + tempNode.value + " ");
				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) {
				tempOutputStack.push(new Character(tempNode.value));
				tempStack.push(tempNode);
				tempNode = tempNode.rightChild;
			}else {
				tempNode = (BinaryCharTree)tempStack.pop();
				tempNode = tempNode.leftChild;
			}//of if
		}//of while
		
		while (!tempOutputStack.isEmpty()) {
			System.out.println(" " + tempOutputStack.pop() + " ");
		}//of while
	}//of postOrderVisitWithStack
	
	
	public static void main(String args[]) {
		BinaryCharTree tempTree = manualConstructTree();
		
		System.out.println("rnPre-order visit:");
		tempTree.preOrderVisit();
		
		System.out.println("rnIn-order visit:");
		tempTree.inOrderVisit();
		
		System.out.println("rnPost-order visit:");
		tempTree.postOrderVisit();
		
		int tempDepth = tempTree.getDepth();
		System.out.println("nThe depth is: " + tempDepth);
		
		System.out.println("rThe number of nodes for the binary tree is: " + tempTree.getNumNodes());
		
		tempTree.toDataArrays();
		System.out.println("The values are: " + Arrays.toString(tempTree.valueArray));
		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.valueArray));
	   	System.out.println("The indices are: " + Arrays.toString(tempTree.indicesArray));
	   	
		tempTree.toDataArrayGenericQueue();
		System.out.println("Generic queue.");
	   	System.out.println("The values are: " + Arrays.toString(tempTree.valueArray));
	   	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};
	   	char[] tempCharArray = {'a','b','c','d','e','f','g'};
	   	int[] tempIndicesArray = {0, 1, 2, 4, 5, 9, 10};
	   	BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);
	   	
		System.out.println("rnPre-order 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

先序遍历的思路和昨天的中序遍历一样，在while中用了两个条件，分别控制入栈和出栈，只是输出语句的位置不同，总体来说是一样的。
后续遍历稍微有点儿麻烦，是用了两个栈。要首先明白“如果将前序的左右子树互换, 就可得到 4) 中右左; 再进行逆序, 可以得到 2) 左右中”（解释详见原博客第26天内容https://blog.csdn.net/minfanphd/article/details/116975721）。通过一个栈控制入栈出栈，另一个栈只存储（存储的顺序是中右左），最后将第二个栈的内容输出（逆序输出即为左右中）。