承接上篇：

一、二叉树的遍历

     所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题(比如：打印节点内容）（遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础。）

1、前、中、后序遍历

NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

由上图可知 

前序遍历结果：1 2 4 5 3 6

 中序遍历结果：4 2 5 1 6 3

 后序遍历结果：4 5 2 6 3 1

2、层序遍历

    层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

对于上图层序遍历结果为：1 2 3 4 5  6

二、二叉树的基本操作

以下操作基于上图二叉树来完成（java）

1、首先我们新建一个包名为BinaryTree,在这个包下新建两个类Test 和 TestBinaryTree。

2、我们初始化实现一个内部类：

      public class TreeNode {
         char val;
         TreeNode left;
         TreeNode right;
         TreeNode() {
 
         }
         TreeNode(char val) {
 
             this.val = val;
         }
         TreeNode(char val, TreeNode left, TreeNode right) {
           this.val = val;
           this.left = left;
           this.right = right;
    }
 }
 
    public TreeNode createTree() {//创建二叉树
        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、三种遍历方式的实现

  public void preOrder(TreeNode root){//前序遍历
         if(root == null){
             return;
         }
         System.out.print(root.val+" ");
         preOrder(root.left);
         preOrder(root.right);
    }
 
    public void inOrder(TreeNode root){//中序遍历
        if(root == null){
            return;
        }
        preOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
 
 
    public void postOrder(TreeNode root){//后序遍历
        if(root == null){
            return;
        }
        preOrder(root.left);
        inOrder(root.right);
        System.out.print(root.val+" ");
    }

运行结果：

4、获取树中节点的个数(2种方法)

   // 获取树中节点的个数 两种方法
    public static int nodeSize = 0;
    public int size(TreeNode root) {
        if(root == null) {
            return 0;
        }
        nodeSize++;
        size(root.left);
        size(root.right);
        return nodeSize;
    }
 
    public int size2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int tmp = size2(root.left)+size2(root.right)+1;
        return tmp;
    }

运行结果： 8

5、获取叶子节点的个数(两种方法)

int getLeafNodeCount(TreeNode root) {
        if(root == null) {
            return 0;
        }
        if(root.left == null && root.right == null) {
            return 1;
        }
        int tmp = getLeafNodeCount(root.left) +
                getLeafNodeCount(root.right);
        return tmp;
    }
 
    public static int leafSize = 0;
    void getLeafNodeCount2(TreeNode root) {
        if(root == null) {
            return ;
        }
        if(root.left == null && root.right == null) {
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }

运行结果： 4

6、判断第K层节点的个数（这里判断的是第三层   结果为 4）

    int getKLevelNodeCount(TreeNode root,int k) {
        if(root == null || k <= 0) {
            return 0;
        }
        if(k == 1) {
            return 1;
        }
        int tmp = getKLevelNodeCount(root.left,k-1) +
                getKLevelNodeCount(root.right,k-1);
        return tmp;
    }

7、获取二叉树的高度

// 时间复杂度：O(n) 
public int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    }
 
    // 时间复杂度：O(n)
    public int getHeight2(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return getHeight2(root.left) > getHeight2(root.right)
                ? getHeight2(root.left)+1 : getHeight2(root.right)+1;
    }

运行结果： 4

8、检测值为val的元素是否存在

public TreeNode find(TreeNode root, char val) {
        if(root == null) {
            return null;
        }
        if(root.val == val) {
            return root;
        }
        TreeNode ret1 = find(root.left,val);
        if(ret1 != null) {
            return ret1;
        }
        TreeNode ret2 =  find(root.right,val);
        if(ret2 != null) {
            return ret2;
        }
        return null;
    }
 
    //时间复杂度：O(min(M,N))  P:M  Q:N
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q != null  || p != null && q == null ) {
            return false;
        }
        if(p == null && q == null) {
            return true;
        }
        if(p.val != q.val) {
            return false;
        }
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }