树的递归遍历和非递归遍历-蒲公英云

树的递归遍历和非递归遍历

红太狼 2022-02-27 23:52 488阅读 0赞

public class TreeNode {
    private int value;
    private TreeNode left;
    private TreeNode right;
    public TreeNode(int value, TreeNode left, TreeNode right){
        this.value = value;
        this.left = left;
        this.right = right;
    }
    public int getValue() {
        return value;
    }
    public TreeNode getLeft() {
        return left;
    }
    public TreeNode getRight() {
        return right;
    }
}
public static void main(String[] args) {
        printByNonRecursive();
        printByRecursive();
    }
    private static void printByNonRecursive(){
        TreeNode treeNode = buildTree();
        System.out.println("\n=======非递归访问结果======\n");
        System.out.print("前序:\t");
        preOrderByNonRecursive(treeNode);
        System.out.print("\n中序:\t");
        inOrderByNonRecursive(treeNode);
        System.out.print("\n后序:\t");
        postOrderByNonRecursive(treeNode);
    }
    /**
     * 利用栈保存访问路径
     * node 标示遍历的当前节点，如果当前节点为空，则置为null
     */
    private static void preOrderByNonRecursive(TreeNode root){
        Deque<TreeNode> stack = new LinkedList();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            //遍历，直到左子树为空
            while (node != null){
                System.out.print(node.getValue() + "\t");
                stack.push(node);
                node = node.getLeft();
            }
            //弹出栈顶元素并遍历右子树
            while (!stack.isEmpty()){
                node = stack.pop().getRight();
                //右子树不空，则需要进行右子树的左子树遍历；右子树为空，则继续弹出栈顶元素
                if (node != null){
                    break;
                }
            }
        }
    }
    private static void inOrderByNonRecursive(TreeNode root){
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while(node != null || !stack.isEmpty()){
            //遍历左子树
            while (node != null){
                stack.push(node);
                node = node.getLeft();
            }
            //弹出、访问栈顶元素，并遍历右子树
            while(!stack.isEmpty()){
                node = stack.pop();
                System.out.print(node.getValue() + "\t");
                node = node.getRight();
                if (node != null){
                    break;
                }
            }
        }
    }
    private static void postOrderByNonRecursive(TreeNode root){
        Deque<TreeNode> stack = new LinkedList<>();
        TreeNode node = root;
        while (node != null || !stack.isEmpty()){
            //访问左子树
            while (node != null){
                stack.push(node);
                node = node.getLeft();
            }
            //弹出栈顶指针，访问右子树
            while (!stack.isEmpty()){
                //获取到栈顶元素，但不弹出
                node = stack.peek();
                if(node.getRight() != null){
                    node = node.getRight();
                    break;
                }else{
                    //如果栈顶元素没有右子树则弹出，并且如果是右孩子，还需要弹出其父节点
                    TreeNode right;
                    do {
                        right = stack.pop();
                        System.out.print(right.getValue() + "\t");
                    }while (!stack.isEmpty() && right == stack.peek().getRight());
                    node = null;
                }
            }
        }
    }
    private static void printByRecursive(){
        TreeNode treeNode = buildTree();
        System.out.println("\n=======递归访问结果======\n");
        System.out.print("前序:\t");
        preOrderByRecursive(treeNode);
        System.out.print("\n中序:\t");
        inOrderByRecursive(treeNode);
        System.out.print("\n后序:\t");
        postOrderByRecursive(treeNode);
    }
    private static void preOrderByRecursive(TreeNode node){
        if(node == null){
            return;
        }
        System.out.print(node.getValue() + "\t");
        preOrderByRecursive(node.getLeft());
        preOrderByRecursive(node.getRight());
    }
    private static void inOrderByRecursive(TreeNode node){
        if (node == null){
            return;
        }
        inOrderByRecursive(node.getLeft());
        System.out.print(node.getValue() + "\t");
        inOrderByRecursive(node.getRight());
    }
    private static void postOrderByRecursive(TreeNode node){
        if (node == null){
            return;
        }
        postOrderByRecursive(node.getLeft());
        postOrderByRecursive(node.getRight());
        System.out.print(node.getValue() + "\t");
    }
    /**
     *                          100
     *           50                               80
     *       9      30                 20                  90
     *    3             15        16      25          150
     *               45    12                 30
     *  前序： 100 50 9 3 30 15 45 12 80 20 16 25 30 90 150
     *  中序： 3 9 50 30 45 15 12 100 16 20 25 30 80 150 90
     *  后序： 3 9 45 12 25 30 50 16 30 25 20 150 90 80 100
     */
    private static TreeNode buildTree(){
        TreeNode left = new TreeNode(45, null, null);
        TreeNode right = new TreeNode(12, null, null);
        TreeNode root = new TreeNode(15, left, right);
        root = new TreeNode(30, null, root);
        left = new TreeNode(3, null, null);
        TreeNode r1 = new TreeNode(9, left, null);
        root = new TreeNode(50, r1, root);
        left = new TreeNode(16, null, null);
        right = new TreeNode(25, null, new TreeNode(30, null, null));
        r1 = new TreeNode(80, new TreeNode(20, left, right), new TreeNode(90, new TreeNode(150, null, null), null));
        return new TreeNode(100, root, r1);
    }