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

红太狼 2022-02-27 23:52 351阅读 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);
        }