JAVA는 두 갈래 나무의 전, 중, 후 순서를 반복한다(귀속과 비귀속)

최근 면접에서 두 갈래 나무 뒤에 비귀속 실현 방법을 물어본 적이 있는데, 귀속 해결이 될 줄 알았으면 OK인 줄 알았는데 너무 요행을 바라는 것 같아서 다음 면접을 앞두고 이 문제를 정리해 봤다.
우선 두 갈래 트리의 구조 정의는java 코드는 다음과 같다.

public class Node {  
    private int data;  
    private Node leftNode;  
    private Node rightNode;  
    public Node(int data, Node leftNode, Node rightNode){  
        this.data = data;  
        this.leftNode = leftNode;  
        this.rightNode = rightNode;  
    }  

    public int getData() {  
        return data;  
    }  
    public void setData(int data) {  
        this.data = data;  
    }  
    public Node getLeftNode() {  
        return leftNode;  
    }  
    public void setLeftNode(Node leftNode) {  
        this.leftNode = leftNode;  
    }  
    public Node getRightNode() {  
        return rightNode;  
    }  
    public void setRightNode(Node rightNode) {  
        this.rightNode = rightNode;  
    }  
} 

먼저 전 · 중 · 후 순서가 두루 반복되는 귀속 실현인데, 이것은 그래도 비교적 간단하다

public void theFirstTraversal(Node root) {  //   
        visit(root);  
        if (root.getLeftNode() != null) {  //   
            theFirstTraversal(root.getLeftNode());  
        }  
        if (root.getRightNode() != null) {  //   
            theFirstTraversal(root.getRightNode());  
        }  
    }  
    public void theInOrderTraversal(Node root) {  //   
        if (root.getLeftNode() != null) {  
            theInOrderTraversal(root.getLeftNode());  
        }  
        visit(root);  
        if (root.getRightNode() != null) {  
            theInOrderTraversal(root.getRightNode());  
        }  
    }


    public void thePostOrderTraversal(Node root) {  //   
        if (root.getLeftNode() != null) {  
            thePostOrderTraversal(root.getLeftNode());  
        }  
        if(root.getRightNode() != null) {  
            thePostOrderTraversal(root.getRightNode());  
        }  
        visit(root);  
    }  

그러나 일부 면접관들은 비귀속 실현의 사고방식을 시험할 수 있기 때문에 실제로는 창고의 보조 실현을 빌려야 한다.코드는 다음과 같습니다.

 public void theFirstTraversal_Stack(Node root) {  //   
        Stack stack = new Stack();  
        Node node = root;  
        while (node != null || stack.size() > 0) {  //   
            if (node != null) {   //   
                visit(node);  
                stack.push(node);  
                node = node.getLeftNode();  
            } else {  
                node = stack.pop();  
                node = node.getRightNode();  
            }  
        }  
    }  

    public void theInOrderTraversal_Stack(Node root) {  //   
        Stack stack = new Stack();  
        Node node = root;  
        while (node != null || stack.size() > 0) {  
            if (node != null) {  
                stack.push(node);   //   
                node = node.getLeftNode();  
            } else {  
                node = stack.pop(); //   
                visit(node);  
                node = node.getRightNode(); 
            }  
        }  
    }  

    public void thePostOrderTraversal_Stack(Node root) {   //    
        Stack stack = new Stack();  
        Stack output = new Stack();//   
        Node node = root;  
        while (node != null || stack.size() > 0) {  
            if (node != null) {  
                output.push(node);  
                stack.push(node);                 
                node = node.getRightNode();  
            } else {  
                node = stack.pop();               
                node = node.getLeftNode();
            }  
        }  
        System.out.println(output.size());
        while (output.size() > 0) {

            visit(output.pop());  
        }  
    }


        /**    */    
    protected static void iterativePostorder3(Node p) {    
        Stack stack = new Stack();    
        Node node = p, prev = p;    
        while (node != null || stack.size() > 0) {    
            while (node != null) {    
                stack.push(node);    
                node = node.getLeft();    
            }    
            if (stack.size() > 0) {    
                Node temp = stack.peek().getRight();    
                if (temp == null || temp == prev) {    
                    node = stack.pop();    
                    visit(node);    
                    prev = node;    
                    node = null;    
                } else {    
                    node = temp;    
                }    
            }    

        }    
    }