木の3種類の後序遍歴

再帰的なループの使用

public static void afterOrder(BinaryTree root) {
        if (root == null)
            throw new IllegalArgumentException("      ");
        if (root.getLeft() != null)
            afterOrder(root.getLeft());
        if (root.getRight() != null)
            afterOrder(root.getRight());
        System.out.print(root.getData()+"\t");
    }
}

2つのスタックを使用して巡回

public static void afterOrderUnRecur(BinaryTree root) {
        if (root == null)
            throw new IllegalArgumentException("      ");
        if (root != null) {
            Stack stack1 = new Stack<>();
            Stack stack2 = new Stack<>();
            stack1.push(root);
            while (!stack1.isEmpty()) {
                root = stack1.pop();
                stack2.push(root);
                if (root.getLeft() != null)
                    stack1.push(root.getLeft());
                if (root.getRight() != null)
                    stack1.push(root.getRight());
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().getData() + "\t");
            }
        }
    }

スタックを使用して巡回

 public static void afterOrderUnRecurUseOneStack(BinaryTree root) {
        if (root != null) {
            Stack<BinaryTree> stack = new Stack<>();
            BinaryTree pre = null, curr;
            stack.push(root);
            while (!stack.isEmpty()){
                curr = stack.peek();
                if (pre != curr.getRight() && pre != curr.getLeft() && curr.getLeft() != null){
                    stack.push(curr.getLeft());
                } else if (pre != curr.getRight() && curr.getRight() != null){
                    stack.push(curr.getRight());
                } else {
                    System.out.print(stack.pop().getData()+"\t");
                    pre = curr;
                }
            }
        }
    }