二叉树_3_模拟实现二叉树

3.1 构造方法

        这里我们使用二叉树的孩子表示法：成员变量有val（存储二叉树的值），left（存储二叉树左孩子的引用），right（存储右孩子的引用）。

public class BinaryTree {
    static class TreeNode{
        public char val;//值域
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子
        //构造方法
        public TreeNode(char val) {
            this.val = val;
        }
    }
}

        这里我们还需要在静态内部类外在创建一个根节点root（方便我们后续对二叉树进行操作）。

public class BinaryTree {
    static class TreeNode{
        public char val;//值域
        public TreeNode left;//左孩子
        public TreeNode right;//右孩子

        public TreeNode(char val) {
            this.val = val;
        }
    }
    public TreeNode root;//将来这个引用指向根节点
}

 3.2 创建一颗二叉树

        注意：下面是一棵简单二叉树的创建，但是并不是真正创建二叉树的方式，真正创建二叉树的方式会在下一篇文章中讲解：

    //创建一棵二叉树
    public TreeNode creatTree(){
        TreeNode A = new TreeNode('A');
        TreeNode B= new TreeNode('B');
        TreeNode C = new TreeNode('C');
        TreeNode D = new TreeNode('D');
        TreeNode E = new TreeNode('E');
        TreeNode F = new TreeNode('F');
        TreeNode G = new TreeNode('G');
        TreeNode H = new TreeNode('H');
        A.left = B;
        A.right = C;
        B.left = D;
        B.right = E;
        C.left = F;
        C.right = G;
        E.right = H;
        return A;
    }

        创建好的二叉树如图所示：

3.3  前 中 后 序遍历

        由于这三种遍历在上篇文章中已经讲过这里就不作过多赘述。注意：下面代码都是将二叉树存储在线性表中。

3.3.1 前序遍历

    public List<Character> preOrder(TreeNode root){
        //创建线性表
        List<Character> ret = new ArrayList<>();
        //递归出口
        if(root == null) return ret;
        //先添加根节点
        ret.add(root.val);
        //递归返回左子树
        List<Character> leftTree = preOrder3(root.left);
        //添加左子树
        ret.addAll(leftTree);
        //递归返回右子树
        List<Character> rightTree = preOrder3(root.right);
        //添加右子树
        ret.addAll(rightTree);
        return ret;
    }

3.3.2 中序遍历 

    public List<Character> inorderTraversal(TreeNode root) {
        //创建线性表
        List<Character> ret = new ArrayList();
        //递归出口
        if(root == null) return ret;
        //递归返回左子树
        List<Character> leftTree =  inorderTraversal(root.left);
        //添加左子树
        ret.addAll(leftTree);
        /添加根节点
        ret.add(root.val);
        //递归返回右子树
        List<Character> rightTree =  inorderTraversal(root.right);
        //添加右子树
        ret.addAll(rightTree);
        return ret;
    }

3.3.3 后序遍历

    public List<Character> postorderTraversal(TreeNode root) {
        List<Character> ret = new ArrayList();
        if(root == null) return ret;
        List<Character> leftTree = postorderTraversal(root.left);
        ret.addAll(leftTree);
        List<Character> rightTree = postorderTraversal(root.right);
        ret.addAll(rightTree);
        ret.add(root.val);
        return ret;
    }

3.4 获取树中节点的个数

        相信大家都会想到：定义一个计数器，然后通过前/中/后序遍历遍历一遍二叉树，每经过一个节点就让计数器++这种做法。代码如下：

   int count = 0;
   public int size(TreeNode root){
        if(root == null) return 0;
        count++;
        size(root.left);
        size(root.right);
        return count;
    }

        下面我们讲子问题的思路：当前树的节点=左子树的节点个数+右子树节点个数+1。 

  //子问题思路：要算当前root的节点的个数 = 左子树节点的个数 + 右子树节点的个数 + 1
    public int size2(TreeNode root){
        if(root == null) return 0;
        return size2(root.left) + size2(root.right) + 1;
    }

3.5 获取当前树中叶子节点个数

        那么问题来了：叶子节点如何判定呢？当一个节点的左孩子为null，右孩子为null，那么他就是叶子节点。

        思路1：遍历

    int leafCount = 0;
    public int getLeafNodeCount(TreeNode root){
        if(root == null){
            return 0;
        }
       if(root.right == null && root.left == null){
           leafCount++;
       }else{
           getLeafNodeCount(root.left);
           getLeafNodeCount(root.right);
       }
         return leafCount;
    }

        思路2：树的叶子节点个数 = 左子树的叶子节点个数 + 右子树的叶子节点个数

    public int getLeafNodeCount2(TreeNode root){
       if(root == null) return 0;
        //判定叶子节点
      if(root.left == null && root.right == null) {
          //是叶子节点就返回1
          return 1;
        }
   //返回左右叶子节点的个数
       return getLeafNodeCount2(root.left)+getLeafNodeCount2(root.right);
    }
      

3.6 获取第K层节点的个数

        思路：root第k层的节点个数 =  root.left第k-1层的节点个数+root.right第k-1层的节点个数。

   public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1){
            //当k == 1，说明走到了距离根节点第k层的节点，返回1
            return 1;
        }
        return getKLevelNodeCount(root.left,k-1)+getKLevelNodeCount(root.right, k-1);
    }

3.7 获取二叉树的高度

        思路：获取二叉树的高度可以看成获取左子树和右子树的高度最大值再加1，即二叉树高度 = max[左树高度，右数高度] + 1。

 public int getHeight(TreeNode root){
       if(root == null) return  0;
       //左子树高度
       int leftHeight = getHeight(root.left);
       //右子树高度
       int rightHight = getHeight(root.right);
       return leftHeight > rightHight ?leftHeight + 1 : rightHight + 1;
    }

3.8 检测值为value的节点是否存在

        思路：先序遍历二叉树，找到值为value的节点返回true。

  public boolean find(TreeNode root, char val){
        //递归出口
        if(root == null) return false;
        //值为val返回true
        if(root.val == val){
            return true;
        }
        //判断左子树
        boolean leftFind = find(root.left,val);
        //如果左子树返回一个true就不用遍历右子树，直接返回true
        if(leftFind == true){
            return true;
        }
        //判断右子树
        boolean rightFind = find(root.right,val);
        if(rightFind == true){
            return true;
        }
        return false;
    }

3.9 层序遍历

        思路：创建一个队列，先将根节点A放入，当队列不为空时（循环），弹出节点（创建一个节点cur记录下当前节点）并输出节点的值，然后通过cur依次获取它的左、右节点（B、C）入队，（这里需要判断节点的左右是否为空，如果为空，则不能入队），因为队列不为空，所以会弹出并输出B，并获取它的左右节点入队，如此循环往复就可以完成层序遍历，下面是图解：

        1、先将根节点A入队： 

2、队列不为空，出队并打印A ，获取A的左右节点入队。

 3、出队并打印B，获取B的左右节点入队。

如此循环反复就可以层序遍历完整棵二叉树。 

 public void levelOrder(TreeNode root){
        //队列
       //先放左子树再放右子树
        if(root == null){
            return;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            //ret会随着出队元素的变化而变化
            TreeNode cur = queue.poll();
            System.out.print(cur.val + " ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if (cur.right != null){
                queue.offer(cur.right);
            }
        }
    }

此外，我们还可以将层序遍历的结果存储在二维数组中：

public List<List<TreeNode>> levelOrder1(TreeNode root) {
        //队列
        //先放左子树再放右子树
        List<List<TreeNode>> ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            //ret会随着出栈元素的变化而变化
            //求一下当前队列的大小
            int size = queue.size();
            List<TreeNode> row = new ArrayList<>();
            //只有将当前行入链表完才会执行外部循环
            while (size != 0) {
                //也就是出队列4次    相当于把这层节点都出队了
                TreeNode cur = queue.poll();
                row.add(cur);
                size--;
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
            }
            //当前行已经处理完
            ret.add(row);
        }
    return ret;
    }

3.10 判断一棵树是不是完全二叉树

        思路：创建一个队列，将二叉树中的所有节点包括null全部入队，将不为null的元素出队（注意：这里的null也是节点，它也可以正常出入队），当遇到null停止出队（此时如果是完全二叉树，那么剩余的元素应都为null），再将队列中剩余元素出队，如果其中有不为null的，则说明不是完全二叉树。如图为不是完全二叉树的情况：

完全二叉树的情况： 

        可以看到队列中全部为null 

 // 判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            //将全部元素包括null都放入队列中
            if(cur != null){
              queue.offer(cur.left);
              queue.offer(cur.right);
          }else{//证明遇到null
              break;
          }
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur != null){
                return false;
            }
        }
        return true;
    }