美文网首页
阿健的刷题库函数|MyTree

阿健的刷题库函数|MyTree

作者: 阿健在长安 | 来源:发表于2018-08-17 16:13 被阅读12次
    package wsj;
    /**
     * 当前类所有函数 
     * ------------- 
     * [递归方式][前序]遍历二叉树:preOrderRecur() 
     * [递归方式][中序]遍历二叉树:inOrderRecur()
     * [递归方式][后序]遍历二叉树:posOrderRecur()
     * [非递归方式][前序]遍历二叉树:preOrderUnRecur()
     * [非递归方式][中序]遍历二叉树:inOrderUnRecur()
     * [非递归方式][后序]遍历二叉树:posOrderUnRecur()
     * [按层]遍历二叉树:printByLevel()
     * 由[前序遍历序列]和[中序遍历序列]重建二叉树:buildTreeByPreAndIn()
     * 由[后序遍历序列]和[中序遍历序列]重建二叉树:buildTreeByPosAndIn()
     */
    
    import java.util.LinkedList;
    import java.util.Stack;
    
    //定义二叉树节点
    class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;
    
        public TreeNode(int x) {
            this.value = x;
        }
    }
    
    public class MyTree {
        // [递归方式][前序]遍历二叉树
        public static void preOrderRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            System.out.print(root.value + "-");
            preOrderRecur(root.left);
            preOrderRecur(root.right);
        }
    
        // [递归方式][中序]遍历二叉树
        public static void inOrderRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            inOrderRecur(root.left);
            System.out.print(root.value + "-");
            inOrderRecur(root.right);
        }
    
        // [递归方式][后序]遍历二叉树
        public static void posOrderRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            posOrderRecur(root.left);
            posOrderRecur(root.right);
            System.out.print(root.value + "-");
        }
    
        // [非递归方式][前序]遍历二叉树
        public static void preOrderUnRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode cur = stack.pop();
                System.out.print(cur.value + "-");
                if (cur.right != null) {
                    stack.push(cur.right);
                }
                if (cur.left != null) {
                    stack.push(cur.left);
                }
            }
        }
    
        // [非递归方式][中序]遍历二叉树
        public static void inOrderUnRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
            while (!stack.isEmpty() || cur != null) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                TreeNode node = stack.pop();
                System.out.print(node.value + "-");
                cur = node.right;
            }
        }
    
        // [非递归方式][后序]遍历二叉树
        public static void posOrderUnRecur(TreeNode root) {
            if (root == null) {
                return;
            }
            Stack<TreeNode> stack1 = new Stack<>();
            Stack<TreeNode> stack2 = new Stack<>();
            TreeNode cur = root;
            stack1.push(cur);
            while (!stack1.isEmpty()) {
                TreeNode node = stack1.pop();
                stack2.push(node);
                if (node.left != null) {
                    stack1.push(node.left);
                }
                if (node.right != null) {
                    stack1.push(node.right);
                }
            }
            while (!stack2.isEmpty()) {
                System.out.print(stack2.pop().value + "-");
            }
        }
        // [按层]遍历二叉树
        public static void printByLevel(TreeNode root){
            if (root==null) {
                return;
            }
            LinkedList<TreeNode> queue=new LinkedList<>();
            queue.addLast(root);
            while (!queue.isEmpty()) {
                TreeNode node=queue.pollFirst();
                System.out.print(node.value+"-");
                if (node.left!=null) {
                    queue.addLast(node.left);
                }
                if (node.right!=null) {
                    queue.addLast(node.right);
                }
            }
        }
        // 由[前序遍历序列]和[中序遍历序列]重建二叉树
        public static TreeNode buildTreeByPreAndIn(int[] pre, int[] in) {
            return buildProcess1(pre, 0, pre.length - 1, in, 0, in.length - 1);
        }
    
        private static TreeNode buildProcess1(int[] pre, int preStart, int preEnd,
                int[] in, int inStart, int inEnd) {
            if (preStart > preEnd || inStart > inEnd) {
                return null;
            }
            TreeNode root = new TreeNode(pre[preStart]);
            int i = inStart;
            while (in[i] != pre[preStart]) {
                i++;
            }
            root.left = buildProcess1(pre, preStart + 1, preStart + i - inStart,
                    in, inStart, i - 1);
            root.right = buildProcess1(pre, preStart + i - inStart + 1, preEnd, in,
                    i + 1, inEnd);
    
            return root;
        }
    
        // 由[后序遍历序列]和[中序遍历序列]重建二叉树
        public static TreeNode buildTreeByPosAndIn(int[] pos, int[] in) {
            return buildProcess2(pos, 0, pos.length - 1, in, 0, in.length - 1);
        }
    
        private static TreeNode buildProcess2(int[] pos, int posStart, int posEnd,
                int[] in, int inStart, int inEnd) {
            if (posStart > posEnd || inStart > inEnd) {
                return null;
            }
            TreeNode root = new TreeNode(pos[posEnd]);
            int i = inStart;
            while (in[i] != pos[posEnd]) {
                i++;
            }
            root.left = buildProcess2(pos, posStart, posStart + i - inStart - 1,
                    in, inStart, i - 1);
            root.right = buildProcess2(pos, posStart + i - inStart, posEnd - 1, in,
                    i + 1, inEnd);
    
            return root;
        }
    
        public static void main(String[] args) {
            int[] pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
            int[] in = { 4, 7, 2, 1, 5, 3, 8, 6 };
            int[] pos = { 7, 4, 2, 5, 8, 6, 3, 1, };
            // TreeNode root = buildTreeByPreAndIn(pre, in);
            TreeNode root = buildTreeByPosAndIn(pos, in);
    
            preOrderRecur(root);
            System.out.println();
            preOrderUnRecur(root);
            System.out.println();
    
            inOrderRecur(root);
            System.out.println();
            inOrderUnRecur(root);
            System.out.println();
    
            posOrderRecur(root);
            System.out.println();
            posOrderUnRecur(root);
            System.out.println();
            
            printByLevel(root);
        }
    }
    

    相关文章

      网友评论

          本文标题:阿健的刷题库函数|MyTree

          本文链接:https://www.haomeiwen.com/subject/doktiftx.html