二叉树的深度优先遍历和广度优先遍历

àì夳堔傛蜴生んèń 2022-02-02 05:31 329阅读 0赞

深度优先遍历：前序遍历，中序遍历，后序遍历  
广度优先遍历：层次遍历

定义二叉树node节点：

public class TreeNode {
        private int data;
        private TreeNode right,left;
    
        public int getData() {
            return data;
        }
    
        public void setData(int data) {
            this.data = data;
        }
    
        public TreeNode getRight() {
            return right;
        }
    
        public void setRight(TreeNode right) {
            this.right = right;
        }
    
        public TreeNode getLeft() {
            return left;
        }
    
        public void setLeft(TreeNode left) {
            this.left = left;
        }
    
        public TreeNode(int data) {
            this.data = data;
        }
    }

二叉树遍历方法：

public class TreeNodeDemo {
    
        public static void main(String[] args) {
    
            TreeNode node1 = new TreeNode(1);
            TreeNode node2 = new TreeNode(2);
            TreeNode node3 = new TreeNode(3);
            TreeNode node4 = new TreeNode(4);
            TreeNode node5 = new TreeNode(5);
            TreeNode node6 = new TreeNode(6);
            TreeNode node7 = new TreeNode(7);
            TreeNode node8 = new TreeNode(8);
            node1.setLeft(node2);
            node1.setRight(node3);
            node2.setLeft(node4);
            node2.setRight(node5);
            node5.setLeft(node7);
            node5.setRight(node8);
            node3.setLeft(node6);
    
            preOrderRecur(node1);
            System.out.println();
            preOrderUnRecur(node1);
            System.out.println();
            inOrderRecur(node1);
            System.out.println();
            inOrderUnRecur(node1);
            System.out.println();
            posOrderRecur(node1);
            System.out.println();
            posOrderUnRecur(node1);
            System.out.println();
            levelTraverse(node1);
        }
    
        /**
         * 递归前序遍历 根-左-右
         *
         * @param head
         */
        public static void preOrderRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            System.out.print(head.getData() + " ");
            preOrderRecur(head.getLeft());
            preOrderRecur(head.getRight());
        }
    
        /**
         * 非递归前序遍历 栈实现
         * 反着顺序，pop出栈先进后出
         * 1、先放中节点
         * 2、有右节点放右节点
         * 3、有左节点放左节点
         *
         * @param head
         */
        public static void preOrderUnRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.add(head);
            while (!stack.isEmpty()) {
                TreeNode pop = stack.pop();
                System.out.print(pop.getData() + " ");
                if (pop.getRight() != null) {
                    stack.add(pop.getRight());
                }
                if (pop.getLeft() != null) {
                    stack.add(pop.getLeft());
                }
            }
    
        }
    
        /**
         * 递归中序遍历 左-根-右
         *
         * @param head
         */
        public static void inOrderRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            inOrderRecur(head.getLeft());
            System.out.print(head.getData() + " ");
            inOrderRecur(head.getRight());
        }
    
        /**
         * 非递归中序遍历 栈实现
         * 1、左节点不为null则压入左节点
         * 2、左节点为null时，pop并打印左节点
         * 3、再往右，右节点为null时，pop并打印
         * 4、右节点不为null时，压入右节点
         *
         * @param head
         */
        public static void inOrderUnRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || head != null) {
                if (head != null) {
                    stack.add(head);
                    head = head.getLeft();
                } else {
                    head = stack.pop();
                    System.out.print(head.getData() + " ");
                    head = head.getRight();
                }
            }
        }
    
        /**
         * 递归后序遍历 左-右-根
         *
         * @param head
         */
        public static void posOrderRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            posOrderRecur(head.getLeft());
            posOrderRecur(head.getRight());
            System.out.print(head.getData() + " ");
        }
    
        /**
         * 非递归后序遍历 栈实现
         * 和前序遍历一样的只不过是使用了两个栈
         * 1、在前序遍历的时候将 中 右 左 节点压栈
         * 2、在原来是打印的地方不打印，将本该打印的节点压到第二个栈中
         * 3、这样第二个栈的出栈顺序就是 左 右 中了
         *
         * @param head
         */
        public static void posOrderUnRecur(TreeNode head) {
            if (head == null) {
                return;
            }
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            stack1.add(head);
            while (!stack1.isEmpty()) {
                head = stack1.pop();
                stack2.add(head);
                if (head.getLeft() != null) {
                    stack1.add(head.getLeft());
                }
                if (head.getRight() != null) {
                    stack1.add(head.getRight());
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().getData() + " ");
            }
        }
    
        /**
         * 层序遍历 队列实现
         * 先进先出
         *
         * @param head
         */
        public static void levelTraverse(TreeNode head) {
            if (head == null) {
                return;
            }
            LinkedList<TreeNode> queue = new LinkedList<>();
            queue.add(head);
            while (!queue.isEmpty()) {
                TreeNode poll = queue.poll();
                System.out.print(poll.getData() + " ");
                if (poll.getLeft() != null) {
                    queue.add(poll.getLeft());
                }
                if (poll.getRight() != null) {
                    queue.add(poll.getRight());
                }
            }
        }
    }