二叉树-前、中、后序遍历。JAVA实现

参考链接：

https:///m0_37741420/article/details/107705009 https:///bobozai86/article/details/116174775 https:///m0_61630116/article/details/124877205

一、递归实现

public class RecursiveSearch {


    /**
     * @Description: 前序遍历
     * @param rt
     * @return: void
     * @author: jc
     * @date: 2022/8/31 16:31
     **/
    public static void preOrderPrint(Tree rt){
        if(rt != null){
            System.out.print(rt.value + " ");
            preOrderPrint(rt.left);
            preOrderPrint(rt.right);
        }
    }


    /**
     * @Description: 中序遍历
     * @param rt
     * @return: void
     * @author: jc
     * @date: 2022/8/31 16:31
     **/
    public static void midOrderPrint(Tree rt){
        if(rt != null){
            midOrderPrint(rt.left);
            System.out.print(rt.value + " ");
            midOrderPrint(rt.right);
        }
    }


    /**
     * @Description: 后序遍历
     * @param rt
     * @return: void
     * @author: jc
     * @date: 2022/8/31 16:31
     **/
    public static void pastOrderPrint(Tree rt){
        if(rt != null){
            pastOrderPrint(rt.left);
            pastOrderPrint(rt.right);
            System.out.print(rt.value + " ");
        }
    }

}

二、非递归实现

public class IterationSearch {

    //非递归的前序遍历
    public static List<Integer> preOrderPrint(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<Tree> stack = new Stack<>();
        stack.push(root);
        while (!stack.empty()) {
            Tree cur = stack.pop();
            list.add(cur.value);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return list;

    }

    //非递归的中序遍历
    public static List<Integer> minOrderPrint(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<Tree> stack = new Stack<>();
        Tree cur = root;
        while (!stack.empty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Tree top = stack.pop();
            list.add(top.value);
            cur = top.right;
        }
        return list;
    }

    //非递归的后序遍历
    public static List<Integer> poseOrderPrint(Tree root) {
        List<Integer> list = new ArrayList<>();
        if (root == null) {
            return list;
        }
        Stack<Tree> stack = new Stack<>();
        Tree cur = root;
        Tree prev = null;
        while (!stack.empty() || cur != null) {
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            Tree top = stack.peek();
            if (top.right == null || top.right == prev) {
                stack.pop();
                prev = top;
                list.add(top.value);
            } else {
                cur = top.right;
            }
        }
        return list;
    }


}

Tree：

public class Tree {

     int value;
     Tree left;
     Tree right;

     public Tree(int value){
         this.value =value;
     }

}