二叉树遍历

二叉树 binary tree ： 每个节点最多有 2 个孩子节点

名词：

根的节点
根的子树
叶子节点 ： 没有“孩子” 的 leaf
父节点 parent
兄弟节点： sibling
孩子节点： child
树的高度
左孩子 left child
右孩子 right child

满二叉树 ： 一个二叉树的所有非叶子节点都存在左右孩子，并且所有的叶子节点都在同一个层级上。。。每一个分支都是满的
完全二叉树：对一个有 n 个节点的二叉树，按层级顺序编号，所有的编号从1 到 n ，，如果这个树的所有节点和同样深度的满二叉树的编号 从1到n 节点位置相同，则是完全二叉树
二叉查找树 binary search tree： 对于一个节点分布均衡的二叉查找树，如果节点总数是n，那么时间复杂度为O(logn),和树的深度一样
二叉查找树，又称 二叉排序树 binary sort tree
二叉堆： 一种特殊的完全二叉树，用数组存储，只要求父节点比它的左右孩子都大
二叉树自平衡： 红黑树，AVL树，数堆

二叉树遍历

在计算机程序中，遍历本身是一个线性操作，所以遍历同样具有线性结构的数组或链表，是件轻而易举的事
二叉树： 典型的非线性数据结构，遍历时需要将非线性关联节点转化成一个线性的序列

• 深度优先遍历 ： 纵深，一头扎到底
  • 前序
    根节点在最前面，从左到右
  • 中序
  • 后序
• 广度优先遍历
  • 层序遍历 ：二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点

绝大多数可以用递归解决的问题，其实都可以用栈 解决
因为：递归和栈都有回溯的特性

代码：
递归遍历：

public class BinaryTreeDemo {
    
    private static class TreeNode{
    
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
    
            this.data = data;
        }
    }

    // 创建binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
    
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
    
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
    
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }

    // 前序
    public static void preOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        System.out.println(node.data);
        preOrderTraveral(node.leftChild);
        preOrderTraveral(node.rightChild);

    }

    // 中序
    public static void inOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        inOrderTraveral(node.leftChild);
        System.out.println(node.data);
        inOrderTraveral(node.rightChild);
    }

    // 后序
    public static void postOrderTraveral(TreeNode node){
    
        if (node == null){
    
            return;
        }
        postOrderTraveral(node.leftChild);
        postOrderTraveral(node.rightChild);
        System.out.println(node.data);
    }

    public static void main(String[] args) {
    
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println("前序遍历");
        preOrderTraveral(node);
        System.out.println("中序遍历");
        inOrderTraveral(node);
        System.out.println("后序遍历");
        postOrderTraveral(node);
    }
}

栈遍历：

public class BinaryTreeStack {
    
    private static class TreeNode{
    
        int data;
        TreeNode leftChild;
        TreeNode rightChild;

        public TreeNode(int data) {
    
            this.data = data;
        }
    }

    // 先序
    public static  void preOrderTraveralWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
    

            while (treeNode != null){
    
                System.out.println(treeNode.data);
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }

            if (!stack.isEmpty()){
    
                treeNode = stack.pop();
                treeNode = treeNode.rightChild;
            }

        }
    }

    // 中序
    public static void inOrderTraveralWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        while (treeNode != null || !stack.isEmpty()){
    
            if (treeNode != null){
    
                stack.push(treeNode);
                treeNode = treeNode.leftChild;
            }else{
    
                 treeNode = stack.pop();
                System.out.println("----"+treeNode.data);
                treeNode = treeNode.rightChild;
            }
        }
    }

    /** * 后序遍历 ： 顺序 左--右--根 * 先序遍历 ： 顺序 根--左--右 * 这里我们可以想到，将先序遍历微调为： 根 -- 右 -- 左。。 然后将这些节点 出栈 ，，push到一个反向栈中，调换顺序 * 这个微调很简单，只是在push节点到栈时，先push左节点，再push右节点，，此时栈顶是右节点，，，先弹出的是右节点，再push * 到反向栈stackReverse中，再push节点 * 核心: 我们只需要增加一个栈来反向输出微调之后的先序遍历的每个节点，就可以得到后序遍历 */
    public static void postOrderBinaryTreeWithStack(TreeNode root){
    
        Stack<TreeNode> stack = new Stack<>();
        TreeNode treeNode = root;
        Stack<TreeNode> stackReverse = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        stack.push(root);
        while (!stack.isEmpty()){
    
            treeNode = stack.pop();
            stackReverse.push(treeNode);
            // stack中右边先取出来，，stackReverse中右边先放进去，后取出来
            if (treeNode.leftChild != null){
    
                stack.push(treeNode.leftChild);
            }
            if (treeNode.rightChild != null){
    
                stack.push(treeNode.rightChild);
            }
        }

        while (!stackReverse.isEmpty()){
    
            treeNode = stackReverse.pop();
            list.add(treeNode.data);
        }
        System.out.println(list);


    }

    // 创建binary tree
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList){
    
        TreeNode  node = null;
        if (inputList == null || inputList.isEmpty()){
    
            return null;
        }
        Integer data = inputList.removeFirst();
        if (data != null){
    
            node = new TreeNode(data);
            node.leftChild = createBinaryTree(inputList);
            node.rightChild = createBinaryTree(inputList);
        }

        return node;
    }


    // 层序遍历
    public static void levelOrderTraversalWithQueue(TreeNode root){
    
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
    
            TreeNode node = queue.poll();
            System.out.println(node.data);
            if (node.leftChild != null){
    
                queue.offer(node.leftChild);
            }
            if (node.rightChild != null){
    
                queue.offer(node.rightChild);
            }
        }
    }

    // 一个层级 ：一个集合
   static ArrayList<List<Integer>> levels = new ArrayList<>();
    // 层序遍历-递归
    public static void levelOrderTraversal(TreeNode node,int level){
    
        if (levels.size() == level) {
    
            // start the current level
            levels.add(new ArrayList<Integer>());
        }
            // 填充数据
            levels.get(level).add(node.data);

            if (node.leftChild != null){
    
                levelOrderTraversal(node.leftChild,level+1);
            }
            if (node.rightChild != null){
    
                levelOrderTraversal(node.rightChild,level+1);
            }

        System.out.println("levels = " + levels);
    }


    public static void levelOrderTraversal(TreeNode root){
    
        if (root == null){
    
            return;
        }
        levelOrderTraversal(root,0);
    }

    public static void main(String[] args) {
    
        LinkedList<Integer> inputList = new LinkedList<>(Arrays.asList(3,2,9,null,null,10,null,null,8,null,4));
        TreeNode node = createBinaryTree(inputList);
        System.out.println("前序遍历");
        preOrderTraveralWithStack(node);
        System.out.println("中序");
        inOrderTraveralWithStack(node);
        System.out.println("后序");
        postOrderBinaryTreeWithStack(node);
        System.out.println("层序遍历");
        levelOrderTraversalWithQueue(node);
        System.out.println("层序遍历--2");
        levelOrderTraversal(node);

    }
   
}

后序遍历： 使用一个反向栈
层序遍历： 使用队列，将子节点offer()进去就出队