数据结构——二叉树的构建+四种遍历（递归、非递归）

女爷i 2022-02-22 14:56 123阅读 0赞

## 二叉树的结构定义 ##

package com.kexin.common;
    
    /**
     * @Author KeXin
     * @Date 2019/4/4 上午10:51
     **/
    public class TreeNode {
    
        char val;
    
        TreeNode left;
        TreeNode right;
    
        public TreeNode(char x) {
            val = x;
        }
    
        public char getVal() {
            return val;
        }
    
        public void setVal(char val) {
            this.val = val;
        }
    
        public TreeNode getLeft() {
            return left;
        }
    
        public void setLeft(TreeNode left) {
            this.left = left;
        }
    
        public TreeNode getRight() {
            return right;
        }
    
        public void setRight(TreeNode right) {
            this.right = right;
        }
    }

## 二叉树的构建+四种遍历（递归、非递归） ##

package com.kexin.code;
    
    import com.kexin.common.TreeNode;
    
    import java.util.*;
    
    /**
     * @Author KeXin
     * @Date 2019/4/4 上午10:51
     **/
    public class BinaryTree {
    
        private static TreeNode buildTree(TreeNode treeNode, int flag) {
            System.out.println("输入" + treeNode.getVal() + (flag <= 0 ? "的左子树" : "的右子树") + " 输入#为空");
            Scanner scanner = new Scanner(System.in);
            String val = scanner.next();
            if (val.equals("#")) return null;
            TreeNode node = new TreeNode(val.charAt(0));
            node.setLeft(buildTree(node, 0));
            node.setRight(buildTree(node, 1));
            return node;
        }
    
        public static void main(String[] args) {
            System.out.println("Input root node ");
            Scanner scanner = new Scanner(System.in);
            String val = scanner.nextLine();
            TreeNode root = new TreeNode(val.charAt(0));
            root.setLeft(buildTree(root, 0));
            root.setRight(buildTree(root, 1));
            printTree(root);
            System.out.println("中序遍历-递归");
            inorderTraversal(root);
            System.out.println("\n中序遍历-非递归");
            List<Integer> list = inorderTraversal2(root);
            for (Integer integer : list) {
                System.out.print(integer);
            }
        }
    
        /**
         * 层序遍历--自上向下
         * <p>
         *
         * @param root
         */
        private static void printTree(TreeNode root) {
            System.out.println("层序遍历");
            List<TreeNode> stack = new ArrayList<TreeNode>();
            List<TreeNode> list = new ArrayList<TreeNode>();
            stack.add(root);
            while (stack.size() != 0) {
                for (int i = 0; i < stack.size(); i++) {
                    TreeNode current = stack.get(i);
                    if (current != null) {
                        System.out.print(current.getVal());
                        list.add(current.getLeft());
                        list.add(current.getRight());
                    }
                }
                stack.clear();
                stack.addAll(list);
                list.clear();
            }
            System.out.println();
        }
    
        /**
         * 层序遍历--自上向下
         * 非递归-队列
         *
         * @param root
         * @return
         */
        private static List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            while (queue.size()>0) {
                int size = queue.size();
                List<Integer> levelList = new ArrayList<Integer>();
                while (size>0){
                    root = queue.remove();
                    if (root != null) {
                        levelList.add(Integer.parseInt(root.getVal() + ""));
                        if (root.getLeft() != null){
                            queue.add(root.getLeft());
                        }
                        if (root.getRight() != null){
                            queue.add(root.getRight());
                        }
                    }
                    size--;
                }
                if(levelList.size()>0) result.add(new ArrayList<Integer>(levelList));
            }
            return result;
        }
    
        /**
         * 层序遍历--自下向上
         * 非递归-队列
         *
         * @param root
         * @return
         */
        private static List<List<Integer>> levelOrderBottom(TreeNode root) {
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            while (queue.size()>0) {
                int size = queue.size();
                List<Integer> levelList = new ArrayList<Integer>();
                while (size>0){
                    root = queue.remove();
                    if (root != null) {
                        levelList.add(Integer.parseInt(root.getVal() + ""));
                        if (root.getLeft() != null){
                            queue.add(root.getLeft());
                        }
                        if (root.getRight() != null){
                            queue.add(root.getRight());
                        }
                    }
                    size--;
                }
                if(levelList.size()>0) result.add(0,new ArrayList<Integer>(levelList));
            }
            return result;
        }
    
        /**
         * 前序遍历
         * 递归
         *
         * @param root
         * @return
         */
        private static List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            if(root==null) return result;
            result.add(Integer.parseInt(root.getVal()+""));
            if(root.getLeft()!=null) result.addAll(preorderTraversal(root.getLeft()));
            if(root.getRight()!=null) result.addAll(preorderTraversal(root.getRight()));
            return result;
        }
        /**
         * 前序遍历
         * 非递归
         *
         * @param root
         * @return
         */
        private static List<Integer> preorderTraversal1(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            while (!stack.empty()||root!=null){
                if(root!=null){
                    stack.push(root);
                    result.add(Integer.parseInt(root.getVal() + ""));
                    root = root.getLeft();
                }else{
                    root = stack.pop();
                    root = root.getRight();
                }
            }
            return result;
        }
    
        /**
         * 中序遍历
         * 递归
         *
         * @param root
         * @return
         */
        private static List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            if(root==null) return result;
            if(root.getLeft()!=null) result.addAll(inorderTraversal(root.getLeft()));
            result.add(Integer.parseInt(root.getVal()+""));
            if(root.getRight()!=null) result.addAll(inorderTraversal(root.getRight()));
            return result;
        }
    
        /**
         * 中序遍历
         * 非递归
         *
         * @param root
         * @return
         */
        private static List<Integer> inorderTraversal2(TreeNode root) {
            List<Integer> list = new ArrayList<Integer>();
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode currentNode = root;
            while (currentNode != null || !stack.isEmpty()) {
                if (currentNode != null) {
                    stack.push(currentNode);
                    currentNode = currentNode.getLeft();
                } else {
                    currentNode = stack.pop();
                    list.add(Integer.parseInt(currentNode.getVal() + ""));
                    currentNode = currentNode.getRight();
                }
            }
            return list;
        }
    
        /**
         * 后序遍历
         * 递归
         *
         * @param root
         * @return
         */
        private List<Integer> postorderTraversal(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            if(root==null) return result;
            if(root.getLeft()!=null) result.addAll(postorderTraversal(root.getLeft()));
            if(root.getRight()!=null) result.addAll(postorderTraversal(root.getRight()));
            result.add(Integer.parseInt(root.getVal()+""));
            return result;
        }
        /**
         * 后序遍历
         * 非递归
         *
         * @param root
         * @return
         */
        private List<Integer> postorderTraversal1(TreeNode root) {
            List<Integer> result = new ArrayList<Integer>();
            if(root==null) return result;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode lastNodeVistited = null;
            while (root!=null||!stack.empty()){
                if(root!=null){
                    stack.push(root);
                    root = root.getLeft();
                }else {
                    root = stack.peek();
                    //如果没有右孩子或者右孩子已经遍历过，就取栈顶元素遍历
                    if(root.getRight()==null||root.getRight()==lastNodeVistited){
                        result.add(Integer.parseInt(root.getVal()+""));
                        lastNodeVistited = stack.pop();
                        root = null;
                    }else{
                        root = root.getRight();
                    }
                }
            }
            return result;
        }
    
    }