抄代码DAY19 二叉树深度遍历的栈实现 (先序和后序)

昨天写了二叉树非递归（利用栈）的中序遍历。今天学习利用栈实现前序和后序。在我数据结构学习的过程中，没有接触过除了前中后三种遍历以外其他的遍历，因为习惯默认都是先左后右。浅谈一下前序和后序：

（代码时在昨天的代码上继续的）

前序：中左右的顺序。当栈不空或者树中节点尚未访问完时，进入循环。若树中节点尚未访问，访问数中节点并将其打印输出，再将该节点入栈，访问其左孩子。执行此循环，直至其无左孩子（左孩子为空），将栈顶元素出栈，访问出栈节点的右孩子。执行以上循环。当树中节点全部访问结束且栈空，结束while循环。

1.  
   public void preOrderVisitWithStack() {
2.  
   ObjectStack tempStack = new ObjectStack();
3.  
   BinaryCharTree tempNode = this;
4.  
    
5.  
   while (!tempStack.isEmpty() || tempNode != null) {
6.  
   if (tempNode != null) {
7.  
   System.out.print("" tempNode.value " ");//打印
8.  
   tempStack.push(tempNode);//入栈
9.  
   tempNode = tempNode.leftChild;//访问其左孩子
10.  
    } else {
11.  
    tempNode = (BinaryCharTree) tempStack.pop();//栈顶元素出栈
12.  
    tempNode = tempNode.rightChild;//访问出栈元素的右孩子
13.  
    }
14.  
    }
15.  
    }
16.  
    ————————————————
17.  
    版权声明：本文为CSDN博主「闵帆」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
18.  
    原文链接：https://blog.csdn.net/minfanphd/article/details/116975721

后序：思想为将先序（中左右）的左右顺序互换得到：中右左   再进行逆置为：左右中，得到后序遍历。

逆置时，利用栈进行逆置。将一列元素全部依次入栈，再输出，就得到了逆置后的元素序列。

1.  
   public void postOrderVisitWithStack() {
2.  
   ObjectStack tempStack = new ObjectStack();
3.  
   BinaryCharTree tempNode = this;
4.  
   ObjectStack tempOutputStack = new ObjectStack();//逆置栈
5.  
    
6.  
   while (!tempStack.isEmpty() || tempNode != null) {
7.  
   if (tempNode != null) {
8.  
   //Store for output.
9.  
   tempOutputStack.push(new Character(tempNode.value));
10.  
    tempStack.push(tempNode);//入栈
11.  
    tempNode = tempNode.rightChild;//访问节点右孩子
12.  
    } else {
13.  
    tempNode = (BinaryCharTree) tempStack.pop();//出栈
14.  
    tempNode = tempNode.leftChild;//访问节点左孩子
15.  
    }
16.  
    }
17.  
     
18.  
    //逆置
19.  
    while (!tempOutputStack.isEmpty()) {
20.  
    System.out.print("" tempOutputStack.pop() " ");
21.  
    }
22.  
    }
23.  
    ————————————————
24.  
    版权声明：本文为CSDN博主「闵帆」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
25.  
    原文链接：https://blog.csdn.net/minfanphd/article/details/116975721

mian方法：

1.  
   public static void main(String args[]) {
2.  
   BinaryCharTree tempTree = manualConstructTree();
3.  
   System.out.println("\r\nPreorder visit:");
4.  
   tempTree.preOrderVisit();
5.  
   System.out.println("\r\nIn-order visit:");
6.  
   tempTree.inOrderVisit();
7.  
   System.out.println("\r\nPost-order visit:");
8.  
   tempTree.postOrderVisit();
9.  
    
10.  
    System.out.println("\r\n\r\nThe depth is: " tempTree.getDepth());
11.  
    System.out.println("The number of nodes is: " tempTree.getNumNodes());
12.  
     
13.  
    tempTree.toDataArrays();
14.  
    System.out.println("The values are: " Arrays.toString(tempTree.valuesArray));
15.  
    System.out.println("The indices are: " Arrays.toString(tempTree.indicesArray));
16.  
     
17.  
    tempTree.toDataArraysObjectQueue();
18.  
    System.out.println("Only object queue.");
19.  
    System.out.println("The values are: " Arrays.toString(tempTree.valuesArray));
20.  
    System.out.println("The indices are: " Arrays.toString(tempTree.indicesArray));
21.  
     
22.  
    char[] tempCharArray = { 'A', 'B', 'C', 'D', 'E', 'F' };
23.  
    int[] tempIndicesArray = { 0, 1, 2, 4, 5, 12 };
24.  
    BinaryCharTree tempTree2 = new BinaryCharTree(tempCharArray, tempIndicesArray);
25.  
     
26.  
    System.out.println("\r\nPre-order visit:");
27.  
    tempTree2.preOrderVisit();
28.  
    System.out.println("\r\nIn-order visit:");
29.  
    tempTree2.inOrderVisit();
30.  
    System.out.println("\r\nPost-order visit:");
31.  
    tempTree2.postOrderVisit();
32.  
     
33.  
    System.out.println("\r\nIn-order visit with stack:");
34.  
    tempTree2.inOrderVisitWithStack();
35.  
    System.out.println("\r\nPre-order visit with stack:");
36.  
    tempTree2.preOrderVisitWithStack();
37.  
    System.out.println("\r\nPost-order visit with stack:");
38.  
    tempTree2.postOrderVisitWithStack();
39.  
    }

结果：

1.  
   Preorder visit:
2.  
   a b d f g c e
3.  
   In-order visit:
4.  
   b f d g a e c
5.  
   Post-order visit:
6.  
   f g d b e c a
7.  
    
8.  
   The depth is: 4
9.  
   The number of nodes is: 7
10.  
    The values are: [a, b, c, d, e, f, g]
11.  
    The indices are: [0, 1, 2, 4, 5, 9, 10]
12.  
    tempIndex = 0
13.  
    Only object queue.
14.  
    The values are: [a, b, c, d, e, f, g]
15.  
    The indices are: [0, 1, 2, 4, 5, 9, 10]
16.  
    indices 0 vs. 1
17.  
    Linking 0 with 1
18.  
    indices 0 vs. 2
19.  
    Linking 0 with 2
20.  
    indices 0 vs. 4
21.  
    indices 1 vs. 4
22.  
    Linking 1 with 3
23.  
    indices 0 vs. 5
24.  
    indices 1 vs. 5
25.  
    indices 2 vs. 5
26.  
    Linking 2 with 4
27.  
    indices 0 vs. 12
28.  
    indices 1 vs. 12
29.  
    indices 2 vs. 12
30.  
    indices 4 vs. 12
31.  
    indices 5 vs. 12
32.  
    Linking 4 with 5
33.  
     
34.  
    Preorder visit:
35.  
    A B D C E F
36.  
    In-order visit:
37.  
    B D A E F C
38.  
    Post-order visit:
39.  
    D B F E C A
40.  
    In-order visit with stack:
41.  
    B D A E F C
42.  
    Pre-order visit with stack:
43.  
    A B D C E F
44.  
    Post-order visit with stack:
45.  
    D B F E C A

实现其他的输出如法炮制。

这篇好文章是转载于：学新通技术网