在实现二叉树之前，我们要对其有充分了解：

1.什么是二叉树？

·简单来说，二叉树就是带两个分支的链表，每个节点里存着一个数据，而每个节点又有两个用引用串联起来的子节点（左孩子和右孩子），孩子里面也同样存着数据，而孩子又有孩子....

2.二叉树的优点

·顺序表查找快但增删慢

·链表查找慢但增删快

·二叉树是完美融合二者优点的一种数据结构，其既保持了链表灵活的结构，使得自身增删快，又能通过层级分布实现高效查询数据

二叉树概念图：

二叉树的灵魂就是递归，整个二叉树的底层实现大多都离不开递归

1.定义节点

我们需要像链表一样，利用静态内部类描述出一个个节点TreeNode：

public class MyBinarryTree {
  public static class TreeNode{
      public char val;

      public TreeNode left;

      public TreeNode right;

      public TreeNode(char val){
          this.val = val;
      }
  }

  public static int usedSize;
}

2.实现接口

接口里包含了接下来要实现的所有方法，在这篇博客充当目录的存在

public interface IBinarryTree {
   1.void preOrder(TreeNode root); 前序遍历 打印

   2.void inOrder(TreeNode root);中序遍历 打印

   3.void postOrder(TreeNode root); 后序遍历 打印

   4.void levelOrder(TreeNode root);层序遍历 自上而下，从左到右 打印

   5.int size(TreeNode root);求节点数

   6.int getLeafNodeCount(TreeNode root);获得叶子节点的数量

   7.int getKLeveNodeCount(TreeNode root, int k);.获得二叉树第K层节点个数

   8.int getHeight(TreeNode root);获得二叉树的高度

   9.TreeNode find(TreeNode root, char val);查找节点

   
   public static class TreeNode {
        public char val;
 
        public TreeNode left;

        public TreeNode right;

        public TreeNode(char val) {
            this.val = val;
        }
    }
}

一、前序遍历（preOrder）

概念图（画的不是很好）：

代码实现：

@Override
public void preOrder(IBinarryTree.TreeNode root) {
    if(root==null){
        return;
    }
    System.out.print(root.val+" ");
    preOrder(root.left);
    preOrder(root.right);
}

思路：先从左边开始，遇到节点则打印其中的值，接下来不断递归，顺序为：

A->B->D->E->C->F->G

二、中序遍历（inOrder）

概念图：

代码实现:

@Override
public void inOrder(IBinarryTree.TreeNode root) {
    if(root==null){
        return;
    }
    inOrder(root.left);
    System.out.print(root.val+" ");
    inOrder(root.right);
}

思路：碰到节点先不打印其中的值，先检查这个节点是否还存在左孩子，如果不存在则打印val

D->B->E->A->F->C->G

三、后序遍历（postOrder）

概念图：

代码实现：

@Override
public void postOrder(IBinarryTree.TreeNode root) {
    if(root==null){
        return;
    }
    postOrder(root.left);
    postOrder(root.right);
    System.out.print(root.val+" ");
}

思路：我们碰到节点先不急着打印val，先检查该节点是否无左右孩子，如果左右孩子都为null，则打印val

D->E->B->F->G->C->A

四、层序遍历（levelOrder）

代码实现：

@Override
public void levelOrder(IBinarryTree.TreeNode root) {
     if(root==null){
         return;
     }
    Queue<IBinarryTree.TreeNode> queue = new LinkedList<>();
     queue.offer(root);

     while(!queue.isEmpty()){
         IBinarryTree.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);
         }
     }

思路：层序遍历是一种自上而下，从左到右的打印，所以我们需要借助队列的先进先出的特性，先offer一个根节点，然后将这个根节点cur，poll吐出来并打印的同时检查其是否有左右孩子，如果有，则queue继续offer，cur的左右孩子进来，不断循环，直到队列为空

五、size（求节点个数）

代码实现：

@Override
public int size(IBinarryTree.TreeNode root) {
   if(root==null){
       return 0;
   }
   return size(root.left) + size(root.right) + 1;
}

思路：通过不断递归，直到走到叶子节点的孩子（空气，也就是null），返回0

六、getLeafNodeCount（获得叶子节点个数）

代码实现：

@Override
public int getLeafNodeCount(IBinarryTree.TreeNode root) {
    if(root==null){
        return 0;
    }
    if(root.left==null&& root.right==null){
        return 1;
    }
    return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
}

思路：叶子节点就是左右孩子都为null的节点，所以我们依然利用递归

七、getKlevelNodeCount（获得第K层节点个数）

代码实现：

@Override
public int getKLeveNodeCount(IBinarryTree.TreeNode root, int k) {
     if(root==null){
         return 0;
     }
     if(k==1){
         return 1;
     }
     return getKLeveNodeCount(root.left,k-1) +getKLeveNodeCount(root.right,k-1);
}

利用递归，每走一次递归就令K-1

八、getHeight（获得二叉树的高度）

代码实现：

@Override
public int getHeight(IBinarryTree.TreeNode root) {
    if(root==null){
        return 0;
    }
    int leftH = getHeight(root.left);
    int rightH = getHeight(root.right);
    int maxH = leftH>rightH?leftH:rightH;
    return maxH+1;
}

九、find（查找节点）

代码实现：
 

@Override
public IBinarryTree.TreeNode find(IBinarryTree.TreeNode root, char val) {
   if(root==null){
       return null;
   }
   if(root.val==val){
       return root;
   }
   IBinarryTree.TreeNode cur1 = find(root.left,val);
   if(cur1!=null){
       return cur1;
   }
   IBinarryTree.TreeNode cur2 = find(root.right,val)
       if(cur2!=null){
           return cur2;
       }
    
       return null;
}