import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Stac

缺乏、安全感 2022-05-22 04:16 161阅读 0赞

import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    
    /* Created by Flynnon on 17-2-25. 对二叉树的递归定义、前序、后序、中序、层序遍历方法的归纳 */
    
    /** * 定义节点类 * 为了简单就不定义getter/setter方法了 */
    class Node {
        public int value;
        public Node left;
        public Node right;
    
        public Node() {
            this(0);
        }
    
        public Node(int v) {
            this.value = v;
            this.left = null;
            this.right = null;
        }
    }
    
    /** * 对二叉树进行操作的工具类 */
    class PrintBinaryTree {
    
        //私有化构造函数
        private PrintBinaryTree(){
            throw new RuntimeException("该工具类不应该被实例化");
        }
    
        /** * 层序遍历二叉树（每一行从左到右，整体上从上到下） * 主要思路：利用队列先进先出的性质保存顺序 * @param root 要遍历的二叉树的根节点 */
        public static void levelTraversal(Node root) {
            Queue<Node> q = new LinkedList<>();
            q.add(root);
            while (!q.isEmpty()) {
                Node temp = q.poll();
                if (temp != null) {
                    System.out.print(temp.value + " ");
                    q.add(temp.left);
                    q.add(temp.right);
                }
            }
        }
    
        /** * 前序遍历二叉树（递归） root->left->right * @param root 要遍历的二叉树的根节点 */
        public static void preOrderRec(Node root) {
            if (root == null) {
                return;
            }
            System.out.print(root.value + " ");
            preOrderRec(root.left);
            preOrderRec(root.right);
        }
    
        /** * 前序遍历二叉树（非递归） root->left->right * 主要思路：利用栈保存未打印的节点，然后逐个出栈处理，在此过程中更新栈 * @param root 要遍历的二叉树的根节点 */
        public static void preOrderUnRec(Node root) {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            Node temp;
            while (!stack.empty()) {            //root==null时，只会空转一个循环，因此无需判断
                temp = stack.pop();
                if (temp != null) {
                    System.out.print(temp.value + " ");
                    stack.push(temp.right);     //注意：这里的入栈顺序是先right后left
                    stack.push(temp.left);      // 以保证从栈中取出时为先left后right
                }
            }
        }
    
        /** * 后序遍历二叉树（递归） * @param root 要遍历的二叉树的根节点 */
        public static void postOrderRec(Node root) {
            if (root == null) {
                return;
            }
            postOrderRec(root.left);
            postOrderRec(root.right);
            System.out.print(root.value + " ");
        }
    
        /** * 后序遍历二叉树（非递归） left->right->root * 主要思路：利用栈保存未打印的节点，然后逐个出栈，进行判断，并根据需要更新栈 * 因为是处理完左右子树后，再处理根(回溯)，所以需要一个记录上一个被打印的节点的引用 * @param root 要遍历的二叉树的根节点 */
        public static void postOrderUnRec(Node root) {
            if (root == null) {
                return;
            }
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            //cur:当前节点 pre:上一个被打印的节点
            Node cur, pre = null;
            while (!stack.empty()) {
                //查看（不是取出）栈顶的结点
                cur = stack.peek();
                //如果当前结点没有孩子结点（叶子节点）
                //或者孩子节点都已被打印过（这里不可能出现有两个子节点却只打印了其中一个的情况）
                //说明该打印当前节点了
                if ((cur.left == null && cur.right == null) ||
                        (pre != null && (pre == cur.left || pre == cur.right))) {
                    System.out.print(cur.value + " ");  //打印当前结点
                    stack.pop();                         //被打印的节点（当前节点）出栈
                    pre = cur;                           //更新pre的值
                } else {
                    if (cur.right != null)          //若未轮到当前节点，将当前节点的右节子点、左子节点入栈
                        stack.push(cur.right);      //注意：这里的入栈顺序是先right后left
                    if (cur.left != null)           // 以保证从栈中取出时为先left后right
                        stack.push(cur.left);
                }
            }
        }
    
        /** * 中序遍历二叉树（递归） * @param root 要遍历的二叉树的根节点 */
        public static void inOrderRec(Node root) {
            if (root == null) {
                return;
            }
            inOrderRec(root.left);
            System.out.print(root.value + " ");
            inOrderRec(root.right);
        }
    
        /** * 中序遍历二叉树（非递归） left->root->right * 主要思路：模拟递归的过程，将左子树节点不断的压入栈，直到左叶子，然后处理栈顶节点的右子树 * @param root 要遍历的二叉树的根节点 */
        public static void inOrderUnRec(Node root) {
            Stack<Node> stack = new Stack<>();
            Node cur = root;                    //纯粹是为了好看...JVM会优化
            while (cur != null || !stack.isEmpty()) {  //当root==null时，不会进入循环，因此无需判断
                while (cur != null) {           //从当前节点开始，从上到下将最左边的那一列节点入栈
                    stack.push(cur);
                    cur = cur.left;
                }
                cur = stack.pop();              //取出栈顶的节点（该节点左节点为null，因此现在该打印它）
                System.out.print(cur.value + " ");
                cur = cur.right;                //定位到已打印的节点的右子节点
            }
        }
    
        /** * 前序递归构造二叉树 root->left->right * @param scanner 输入流，用于读取节点值 * @return 构造完成的二叉树的根节点 */
        public static Node createTreeNode(Scanner scanner) {
            assert scanner!=null;
            Node root = null;                 //声明当前根节点
            int data = scanner.nextInt();
            if (data > 0) {                             //若当前节点存在（这里为了简单以负数为占位符）
                root = new Node(data);                  //使用其它顺序构造二叉树，只需更改这三句即可
                root.left = createTreeNode(scanner);
                root.right = createTreeNode(scanner);
            }
            return root;
        }
    }
    
    /** * 测试类 */
    public class BinaryTree{ 
        // 这里以节点值分别为1-7的满二叉树为例
        // 1 2 4 -1 -1 5 -1 -1 3 6 -1 -1 7 -1 -1
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Node root = PrintBinaryTree.createTreeNode(sc);
            sc.close();
            System.out.print("层序遍历:");
            PrintBinaryTree.levelTraversal(root);
            System.out.print("\n中序递归遍历:");
            PrintBinaryTree.inOrderRec(root);
            System.out.print("\n中序非递归遍历:");
            PrintBinaryTree.inOrderUnRec(root);
            System.out.print("\n前序递归遍历:");
            PrintBinaryTree.preOrderRec(root);
            System.out.print("\n前序非递归遍历:");
            PrintBinaryTree.preOrderUnRec(root);
            System.out.print("\n后序递归遍历:");
            PrintBinaryTree.postOrderRec(root);
            System.out.print("\n后序非递归遍历:");
            PrintBinaryTree.postOrderUnRec(root);
        }
    }