二叉树

基本概念

二叉树的定义： 二叉树是由一组数据构成的集合，这些数据要么为空集，要么由根节点和左子树以及右子树构成。其中，左子树和右子树均为二叉树。（树形结构中子树互不相交）

二叉树不存在度大于2的结点，二叉树的子树有左右之分，次序不可以颠倒。

两种特殊的二叉树

满二叉树：如果一棵二叉树的结点要么是叶子结点，要么它有两个子结点，这样的树就是满二叉树。

完全二叉树：完全二叉树（Complete Binary Tree）是指深度为k、有n个结点的二叉树，其结点编号与相同深度的满二叉树对应位置一致，是效率较高的数据结构 。满二叉树每一层的结点数达到最大值时即为完全二叉树的特殊形态 。

二叉树的性质

1. 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有(i>0)个结点
2. 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数是(k>=0)
3. 对任何⼀棵⼆叉树, 如果其叶结点个数为 n0, 度为2的⾮叶结点个数为 n2,则有n0＝n2＋1
4. 具有n个结点的完全⼆叉树的深度k为上取整
5. 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对
   于序号为i的结点有：
   ◦ 若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
   ◦ 若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
   ◦ 若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦

特别注意第五条性质，在构建堆的时候会用到。

建立一个二叉树

为了方便学习，我们直接手动建立一个简单的二叉树。

public class BinaryTree {
    //以内部类的方式创建结点
    static class BinaryTreeNode {
        int val;
        BinaryTreeNode leftChild;
        BinaryTreeNode rightChild;

        public BinaryTreeNode(int val) {
            this.val = val;
        }
    }

    int nodeSize = 0;

    int leafCount = 0;

    //根节点
    public BinaryTreeNode root;

    //手动创建一个二叉树
    public void createTree() {
        BinaryTreeNode node1 = new BinaryTreeNode(1);
        BinaryTreeNode node2 = new BinaryTreeNode(2);
        BinaryTreeNode node3 = new BinaryTreeNode(3);
        BinaryTreeNode node4 = new BinaryTreeNode(4);
        BinaryTreeNode node5 = new BinaryTreeNode(5);
        BinaryTreeNode node6 = new BinaryTreeNode(6);

        root = node1;
        node1.leftChild =  node2;
        node2.leftChild = node3;
        node1.rightChild = node4;
        node4.leftChild = node5;
        node4.rightChild = node6;

    }
  }

我们直接建立一个BinaryTree类，利用静态内部类来定义结点。这样我们可以通过外部类名.内部类名在这个类的外部访问到二叉树的结点数据结构。定义了一个createTree方法，手动创建结点和左右子树的信息。执行了上述的方法之后，我们将会创建如下的一颗二叉树。

上述代码中的nodeSize变量代表了这颗二叉树中结点的数量，leafSize变量代表这颗二叉树中叶子结点的数量。

二叉树的遍历

学习⼆叉树结构，最简单的⽅式就是遍历。所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。访问结点所做的操作依赖于具体的应⽤问题(⽐如：打印节点内
容、节点内容加1)。 遍历是⼆叉树上最重要的操作之⼀，是⼆叉树上进⾏其它运算之基础。

前序遍历

前序遍历的遍历顺序是：先访问根节点，再访问左子树，最后访问右子树。下面我们来看前序遍历的递归写法：

public void preOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }

        //先访问当前结点
        System.out.print(node.val + " ");
        //访问左子树
        preOrder(node.leftChild);
        //访问右子树
        preOrder(node.rightChild);
    }

逻辑并不复杂，首先设置递归出口。如果遍历到null结点直接返回。首先访问根节点，打印根节点的值，随后递归访问左右子树即可。

下面我们来看非递归的前序遍历的写法：

//非递归的前序遍历
    public void preOrderNor(BinaryTreeNode root) {
        //定义一个栈来辅助实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            //首先打印当前结点的值，然后一路向左
            while(cur != null) {
                System.out.print(cur.val + " ");
                stack.push(cur);
                cur = cur.leftChild;
            }

             //代码走到这里，说明该子树中的所有的根节点和左子树均已经访问过了。
            //此时栈顶记录了最后一次访问的结点，将栈顶元素弹出，并让cur指向栈顶元素的右子树的根节点
            //对栈顶元素的右子树进行前序遍历
             BinaryTreeNode top = stack.pop();
             cur = top.rightChild;
        }
    }

我们定义一个栈来辅助前序遍历，每次遍历到一个结点判断当前结点是否为null结点。如果当前结点不为空，则打印当前结点的值，并将当前的结点压入栈，随后让cur指向当前结点的左子树的根节点。若cur指向的结点等于空的话，我们让栈顶元素出栈，随后让cur指向栈顶元素的右子树的根节点。如此循环往复，直到遍历完整颗二叉树。

中序遍历

中序遍历的遍历顺序是：先遍历左子树，再遍历根节点，最后遍历右子树。下面我们首先来看中序遍历的递归写法：

和前序遍历的写法类似：

//中序遍历
    public void inOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }
        
        //先访问左子树
        inOrder(node.leftChild);

        //访问当前节点
        System.out.print(node.val + " ");

        //访问右子树
        inOrder(node.rightChild);
    }

和前序遍历的递归写法类似，如果访问到null结点。直接返回，接下来递归访问左子树，再访问根节点，最后访问右子树。

下面来看非递归的写法：

//非递归的中序遍历
    public void inOrderNor(BinaryTreeNode root) {
        //定义一个栈来辅助实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();

        BinaryTreeNode cur = root;

        while (cur != null || !stack.isEmpty()) {
            while(cur != null) {
                stack.push(cur);
                cur = cur.leftChild;
            }

            //要打印栈顶元素的值
            BinaryTreeNode top = stack.pop();
            System.out.print(top.val + " ");
            cur = top.rightChild;
        }
    }

和前序遍历的非递归写法类似，唯一有区别的是打印结点的时机。前序遍历打印结点的时机是直接访问的时候，中序遍历打印结点的时机是该节点的左子树访问结束了之后。

后序遍历

后序遍历值得注意一下，后序遍历的递归写法和前序遍历和中序遍历类似：先递归访问左子树，然后递归访问右子树，最后访问根节点。

我们来看一下递归的写法：

 public void postOrder(BinaryTreeNode node) {
        //递归出口
        if(node == null) {
            return;
        }

        //先递归访问左子树
        postOrder(node.leftChild);
        //递归访问右子树
        postOrder(node.rightChild);
        //访问当前节点
        System.out.print(node.val + " ");
    }

值得注意的是非递归的写法：

//非递归的后序遍历
    public void postOrderNor(BinaryTreeNode node) {
        //利用栈来实现深度优先遍历
        Stack<BinaryTreeNode> stack = new Stack<>();
        BinaryTreeNode cur = node;
        BinaryTreeNode pre = null;

        while (cur != null || !stack.isEmpty()) {
            //后序遍历，左右根
            while(cur != null) {
                stack.push(cur);
                cur = cur.leftChild;
            }

            //找到了最左端
            //如果右端为空或者已经遍历过了，那么弹栈并打印
            BinaryTreeNode top = stack.peek();
            //判断栈顶元素的右孩子是否为空或者已经遍历过
            if(top.rightChild == null || pre == top.rightChild) {
                //打印
                System.out.print(top.val + " ");
                //更新pre
                pre = top;
                //弹栈
                stack.pop();
            }else {
                cur = top.rightChild;
            }

        }
    }

可以看到二叉树后序遍历的非递归写法和非递归的前序遍历和中序遍历有很大的区别。我们来详细的看一下代码实现：

定义一个栈来辅助遍历，用cur指向当前遍历的结点，用prev指向前一次遍历的结点。当cur != null 或者栈不为空的时候进行循环。

cur不为空的时候一路向左，并将cur所指向的元素压入栈。当右端为空或者已经遍历过（top.rightChild == null || pre == top.rightChild）的时候弹栈并打印，如果右端不为空或者没有遍历过，则让cur指向栈顶元素的右子树的根节点。这一步是为了实现后序遍历的时候右子树在根节点之前进行遍历。当外层的循环走完了之后，整颗二叉树就按照左子树、根节点、右子树的顺序遍历完成了。

层序遍历

层序遍历是按照从左到右，从上到下的顺序遍历二叉树，基础的层序遍历需要借助队列来完成。下面来看代码实现：

 public void levelOrder(BinaryTreeNode root) {
           //处理特殊情况，如果是空树直接return
        if(root == null) {
            return;
        }

        //建立一个辅助队列
        LinkedList<BinaryTreeNode> queue = new LinkedList<>();
        //将根节点入队
        queue.offer(root);

        //当队列不为空的时候
        while(!queue.isEmpty()) {
            //拿出队头元素
            BinaryTreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            //若左子树不为空，将左子树放入队列
            if(cur.leftChild != null) {
                queue.offer(cur.leftChild);
            }

            if(cur.rightChild != null) {
                queue.offer(cur.rightChild);
            }
        }
    }

我们来看一下代码实现：首先处理空值，如果根节点为空的话直接return,新建一个队列辅助遍历，将根节点入队，当队列不为空的时候，循环：定义一个cur指向队头元素，将队头元素出队，打印cur指向的结点值。判断cur的左孩子是否为空，如果不为空则入队，判断cur的右孩子是否为空，如果不为空则入队。当循环结束之后，整个层序遍历完成。

从下到上，从左到右遍历二叉树（反转的层序遍历）

public List<List<Integer>> levelOrderBottom(TreeNode root) {
        //先写一个基本的层序遍历

        //处理根节点为空的情况
        if(root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();
        queue.offer(root);

        while (!queue.isEmpty()) {
            int queueSize = queue.size();
            ArrayList<Integer> curLow = new ArrayList<>();
            for (int i = 0; i < queueSize; i++) {
                //将当前结点的值加入curLow之中
                TreeNode curNode = queue.poll();
                curLow.add(curNode.val);

                if (curNode.left != null) {
                    queue.offer(curNode.left);
                }

                if (curNode.right != null) {
                    queue.offer(curNode.right);
                }
            }

            //更新queueSize
            queueSize = queue.size();
           //将curRow添加到result之中
            result.add(curLow);
        }

        //反转列表
        Collections.reverse(result);
        return result;
    }

上述代码是leetcode上的一道算法题，需要实现从从左到右，从下至上的层序遍历。我们的思路是，用一个二维数组存储遍历的结果，然后将二维数组反转即可。当然了这种说法并不严谨，在实现的时候我们是使用了一个嵌套的List,List的元素是一个一个的List

我们首先定义一个以List 为元素的ArrayList，随后判断根节点是否为空，如果为空，直接返回。然后将根节点入队，为了保存每一层的遍历结果，在while(!queue.isEmpty()) 循环中，定义一个queueSize变量来记录队列当前的容量，再写一个for循环，循环条件为：int i = 0;i < queueSize;i++ ，循环体中定义一个ArrayList来存储当前这一层的遍历结果,接下来和正常的层序遍历一样，将队头元素出队，加入ArrayList之中,判断当前结点的左右子树是否为空，如果不为空则入队。在每一次的for循环结束之后，更新queueSize变量的值，并将curRow添加到嵌套List result之中，在while循环结束之后，嵌套List之中存储的是此二叉树层序遍历的结果，使用Collection接口中的reverse方法。将List反转，此时List之中存储的就是自下而上，从左到右的层序遍历结果。

基本操作

求二叉树的结点的值

算法设计思路：如果当前结点 == null return 0 如果当前结点不为null return func(root.leftChild) + func(root.rightChild) + 1;

递归算法需要注意递归出口：当前算法的递归出口是：if(root == null) return 0;

下面来看代码：

 public int size1(BinaryTreeNode node) {
        if(node == null) {
            return 0;
        }
        
        return size1(node.leftChild) + size1(node.rightChild) + 1;
    }

求二叉树的叶子结点的个数

算法设计思路：采用一种遍历方式遍历二叉树，if(cur.left == null && cur.right == null) return 1; else { return func(cur.leftChild) + func(cur.rightChild)}

下面来看代码实现：

 public int getLeafNodeCount1(BinaryTreeNode root) {
        if(root == null) {
            return 0;
        }

        if(root.leftChild == null && root.rightChild == null) {
            return 1;
        }
        return getLeafNodeCount1(root.leftChild) + getLeafNodeCount1(root.rightChild);
    }

求二叉树第K层结点的个数

算法设计思路：在递归的时候设置一个整数k代表层数，每递归一次k–，当k = 1 就到了指定的层

//获取第k层结点的个数
    public int getKLevelCount(BinaryTreeNode root,int k) {
        //整棵树的第k层 = 左子树的第k - 1 层 + 右子树的k - 1层
        if(root == null) {
            return 0;
        }

        if(k == 1) {
            return 1;
        }

        return getKLevelCount(root.leftChild,k - 1) + getKLevelCount(root.rightChild,k - 1);
    }

求二叉树的高度

算法设计思路：递归写法：if（cur == null ) return 0;

return max(func(leftChild) ,func(rightChild) ) + 1

 public static int getHeight(BinaryTreeNode node) {
        if(node == null) {
            return 0;
        }

        return Math.max(getHeight(node.leftChild),getHeight(node.rightChild)) + 1;
    }