树的遍历【后序遍历】 - 非递归方法实现

曾经终败给现在 2022-05-12 06:20 134阅读 0赞

## 代码 ##

![举例][70]

package com.uj.nsnc.test;
    
    import org.junit.Test;
    
    import java.util.Stack;
    
    public class BinaryTreeTravel { 
    
        class Node{
    
            public Node left;
            public Node right;
            public int value;
    
            Node(Node left, Node right, int value) {
                this.left = left;
                this.right = right;
                this.value = value;
            }
        }
    
        @Test
        public void testBinaryTreeTravel(){
    
            Node node4 = new Node(null,null,2);
            Node node5 = new Node(null,null,1);
            Node node3 = new Node(null, node5, 3);
            Node node2 = new Node(null, node4, 2);
            Node node1 = new Node(node2, node3, 1);
    
            PostOrderTraversalByStack(node1);
        }
    
    
        /*==== 后序遍历 - 非递归实现===*/
        private void PostOrderTraversalByStack(Node tree){
            if(tree==null)
                return;
            Node temp = tree;
            Stack<Node> stack = new Stack<>();
            Stack<Node> result = new Stack<>();
            while (!stack.empty() || temp!=null) {
                /*====右子树压入栈===*/
                while (temp != null) {
                    stack.push(temp);
                    temp = temp.right;
                }
                Node node = stack.pop();
                result.push(node);
                /*=== 当前节点的左子树 ===*/
                temp = node.left;
            }
            while (!result.empty()) {
                System.out.print(result.pop().value + "-");
            }
        }
    }

## 分析 ##

1.  后续遍历。 `左右中` 的次序打印节点，需要来到节点 `3次`。  
    
    
    1.  通过该节点 `遍历左子树` ，通过该节点 `遍历右子树`， 遍历`自身`
2.  在原来 `两次`基础上，叠加一次，如何解决叠加问题？  
    
    
    1.  原来能进行 `两次`的原因是？
    2.  借助了栈 `先进后出` 的特性，先把遍历节点压入栈，而后取出再次遍历
    3.  如果 `3次` 无法实现，采用什么方法？
    4.  `逆序` 后序遍历 - 得到`中右左的顺序`
    5.  怎么求 中右左的顺序？以及怎么`逆序`中右左？
    6.  引入 `栈2`，保存中右左的顺序，依次取出就是后序遍历
    7.  关键是求导 - **中右左**
    8.  中右左 和 `中左右` 【先序遍历】遍历过程中的差别？
    9.  参[考非递归 `中左右` 原理][Link 1]可得
3.  end

[70]: /images/20220512/75e262360135454aa3045a077717fb0e.png
[Link 1]: https://blog.csdn.net/ai_shuyingzhixia/article/details/82711186