有一个特殊的结点，称为根结点，根结点没有前驱结点(通常叫它root节点)
除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。(根节点：唯一，有且仅有一个根节点，中间结点：一个双亲可以有多个孩子节点，叶子结点:叶子结点度为0，无孩子可以有多个)。
由于一棵树又可以划分为多个子树，所以二叉树的操作大部分都是由递归来实现的
对于节点数为n，n>0时根节点是唯一的，有且仅有一个
一棵树可以有多个节点，但是节点之间是不能相交的

树的结点分类

结点的度：一个结点含有子树的个数称为该结点的度；对于1节点它的度就是2,1节点共有两个子树
树的度：一棵树中，所有结点度的最大值称为树的度； 这颗树，一个结点最多子树为2个，所以树的度为2
叶子结点或终端结点：度为0的结点称为叶结点；叶子结点在树的最后没有子树的节点，例如6,7,8,9,10节点.
双亲结点或父结点：若一个结点含有子结点这个结点称为其子结点的父结点;比如2的父亲就是1
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 对于2节点来说它的父亲是1，对于1节点来说它的孩子是2和3节点
根结点：一棵树中，没有双亲结点的结点；一般来说除了空树外，其他树有且仅有一个根节点root
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推
树的深度：相对于节点来说的，比如1节点深度为1。?2,3节点深度为2。4,5,6,7节点深度为3

树的高度：树中结点的最大层次；树的最大深度就是这一颗树的高度

树的祖先：从根到该结点所经分支上的所有结点，对于8节点来说，1,2,4节点都是8的公共祖先。

二叉树

二叉树的特点

对于二叉树的每一个节点来说，它的度也就是子树的个数都是小于等于2的
二叉树有左右子树区分。一定要区分它的左树和右树。

二叉树的五种形态

空树（没有结点的树）
只有左树没有右树
只有右树没有左树
既有左树又有右树
只有一个根节点

三种特殊的二叉树

斜树：所有树只有左子树的树或者只有右子树的树叫做斜树，只有左子树的树叫做左斜树，只有右子树的树叫做右斜树

满二叉树：?一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是，则它就是满二叉树

?完全二叉树：完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。要注意的是满二叉树是一种特殊的完全二叉树。完全二叉树从左往右开始编号，如果不为空是一颗完全二叉树，完全二叉树可以有度为1的情况，如果从左往右开始编号为空，那就证明不是一颗完全二叉树

?二叉树的性质(非常重要)

若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有 2^i-1(i>0)个结点

?若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是2^k-1 (k>=0)

?对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1

?具有n个结点的完全二叉树的深度k为 log2(n+1)上取整

?. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
若2i+1<n，左孩子序号：2i+1，否则无左孩子
若2i+2<n，右孩子序号：2i+2，否则无右孩子

给定子节点下标求父节点下标：(i-1)/2

给定父节点下标求子节点下标：左孩子2i+1 右孩子：2i+2

这个结论在堆的学习经常会用到所以务必要记住

一些习题：

?二叉树的存储

我们在平时刷题时和平常学的一些二叉树基础都是利用链式存储，也就是说一个节点有节点值和它的左孩子和右孩子。

public class TreeNode {
    int val; // 数据域
    TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
    TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}

二叉树的基本操作

首先我们创建一颗二叉树

 static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int val){
            this.val = val;
        }
    }

    //根节点
    public TreeNode root;

    public TreeNode createTree(){
        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(3);
        TreeNode node4 = new TreeNode(4);
        TreeNode node5 = new TreeNode(5);
        TreeNode node6 = new TreeNode(6);
        TreeNode node7 = new TreeNode(7);

        node1.left = node2;
        node1.right = node4;
        node2.left = node3;
        node2.right = node7;
        node4.left = node5;
        node4.right= node6;
        root =node1;
        return root;

    }

二叉树的遍历

二叉树的前序遍历

二叉树的前序遍历：先访问根在访问左子树在访问右子树? 根-左子树-右子树

?对于这样一颗二叉树它的先序遍历时 A - B - D - E -H - C - F - G

?我们仔细分析一下这个前序遍历：

对于A这棵树来说要先访问根也就是A,然后去访问A的左子树，而A的左子树又是一棵树,先访问根B,在访问B这棵树的左子树D,对于D这棵树而言又是一棵树，所以先访问根D,再去访问它的左子树，发现D的左子树为null,再去访问D的右子树为null,所以D这棵树访问完了，也证明B的左树访问完了，然后接着访问B的右树E，而E又是一棵树，先访问根节点E,在去访问它的左子树，发现它的左子树为null,再去访问它的右子树H,所以E这棵树访问完了，也说明B的右树访问完了，也说明A的左树访问完了，然后再去访问A的右树C，而C又是一棵树，先访问根C,在去访问她的左树F,而F又是一棵树，访问它的左树为空，右树为空，F这棵树访问完了，所以C的左树访问完，同理再去访问G,好最后返回到A证明A这棵树走完了，这才是真正的结束一个二叉树的前序遍历。

根据我上面的分析，每一个树的逻辑都是一样的，都是先访问根节点，在访问左子树，在访问右子树，在访问左子树或者右子树，又是同样的道理，所以每一棵树可以用相同的操作，在使用递归操作重复调用，最终这棵树就遍历完成。

代码实现：

前序遍历-->递归版本无list

 // 前序遍历-->递归版本无list
    void preOrder(TreeNode root){
        if(root==null) return;
        System.out.print(root.val+" ");
        preOrder(root.left);
        preOrder(root.right);
    }

使用list遍历思路去存储-->前序遍历

 //使用list遍历思路去存储-->前序遍历
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null) return list;
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }

使用list子问题思路进行前序遍历

//使用list子问题思路进行前序遍历
    public List<Integer> preorderTraversal1(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        if(root==null) return list;
        list.add(root.val);
        List<Integer> leftTree = preorderTraversal(root.left);
        if(leftTree!=null){
            list.addAll(leftTree);
        }
        List<Integer> rightTree = preorderTraversal(root.right);
        if(rightTree!=null){
            list.addAll(rightTree);
        }
        return list;
    }

前序遍历-->非递归版本

//前序遍历-->非递归版本
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||(!stack.isEmpty())){
            while(cur!=null){
                stack.push(cur);
                ret.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            if(top.right!=null){
                cur = top.right;
            }
        }
        return ret;
    }

二叉树的中序遍历

根据二叉树的前序遍历，中序遍历也是一样的道理，中序遍历是先访问左子树在访问根节点在访问右子树。

对于上面那棵树而言中序遍历为：D - B - E - H - A - F - C - G

代码实现：

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

使用list-->子问题进行中序遍历

//使用list-->子问题进行中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        List<Integer> leftTree = inorderTraversal(root.left);
        if(leftTree!=null){
            ret.addAll(leftTree);
        }
        ret.add(root.val);
        List<Integer> rightTree = inorderTraversal(root.right);
        if(rightTree!=null){
            ret.addAll(rightTree);
        }
        return ret;
    }

使用list进行非递归实现--->中序遍历

//使用list进行非递归实现--->中序遍历
    public List<Integer> inorderTraversalNor(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while(cur!=null||!stack.isEmpty()){
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            ret.add(top.val);
            if (top.right != null) {
                cur = top.right;
            }
        }
        return ret;
    }

二叉树的后序遍历

根据二叉树的前序遍历，中序遍历，后序遍历也是一样的道理，后序遍历是先访问左子树在访问右子树在访问根节点。

对于上面那棵树而言后序遍历为：D - H - E - B - F - G - C - A

代码实现：

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

使用非递归来实现二叉树的后序遍历

//使用非递归来实现二叉树的后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root==null) return ret;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur!=null||(!stack.isEmpty())){
            while(cur!=null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();
            if(top.right==null||top.right==prev){
                stack.pop();
                ret.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return ret;
    }

最终我们还可以得出一个结论要想有想构建一颗二叉树，要么给出二叉树的递归序(也就是包括null节点也给出)，否则要想得到一颗二叉树，必须知道中序遍历，要么前序遍历和中序遍历，要么后序遍历和中序遍历，如果没有中序遍历，就只能根据前序或者后序确定根节点，不能确定左子树和右子树。

获取树中节点的个数

对于获取节点个数：普通遍历思路，就是遍历二叉树中的每一个节点然后计数器++，可以使用前序中序后序都可以。

这里的代码实现给出的是子问题的思路，我们可以思考一下，对于一颗二叉树来说，就是根节点，左子树和右子树，那一颗二叉树节点的个数是不是等于左子树节点的个数+右子树节点的个数+根节点本身(也就是+1)。

int size(TreeNode root){
    if(root==null) return 0;
    int left = size(root.left);//算出左子树的节点个数
    int right = size(root.right);//算出右子树的节点个数
    return left+right+1;
}

获取叶子节点的个数

遍历思路：叶子结点前面我也讲过就是度为0的节点，也就是当我们遍历树的左子树为空并且它的右子树为空，那他就是我们的叶子结点使用计数器++就可以。

子问题思路：这里我给出的也是子问题思路，一颗二叉树我们只要求出它的左子树叶子结点个数+右子树叶子结点个数就是我们这棵二叉树的叶子结点个数了。

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

获取第K层节点的个数

对于一颗二叉树，我们要求第3层结点个数，那相对于根节点我们是不是求它的第二层结点。而相对于第二层结点来说我们是不是在求它的第一层结点，对于第三层，我们是求它的第0层。

号也就是说，如果我们求第k层结点的个数我们就求相对于每一层的k-1层结点，当k=1时候也就是求它本身结点个数1.

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

获取二叉树的高度

对于一颗二叉树来说，树的高度就是这颗二叉树最大深度，我们只要求出左子树和右子树高度的最大值在+1就是这棵二叉树的高度。

int getHeight(TreeNode root){
        if(root==null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return left>right?left+1:right+1;
    }

检测值为value的元素是否存在

还是一样的，对于一颗二叉树我们要判断value是否在这颗二叉树中存在，我们首先会先去根节点看一看是不是这个value,如果不是value，再去左子树看一看有没有，再去看一看右子树有没有，如果在一棵树中找到value立马把这个值返回来。

TreeNode find(TreeNode root, int val){
        if(root==null) return null;
        if(root.val==val) return root;
        TreeNode leftTree = find(root.left,val);
        if(leftTree!=null){
            return leftTree;
        }
        TreeNode rightTree = find(root.right,val);
        if(rightTree!=null){
            return rightTree;
        }
        return null;
    }

层序遍历

层序遍历我们利用一个辅助栈来实现。

先将根节点压入栈中
每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，如果为null我们就不压入栈中，反复进行最终就是层序遍历

void levelOrder(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            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);
            }
        }
    }

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

根据层序遍历思想

先将根节点压入栈中
每一次将栈顶元素弹出并打印，在弹出元素时要将弹出元素利用一个临时遍历存起来，然后同时将它的左子树和右子树一并压入栈中，此时与层序遍历不同的是如果树为null，我们依然要压入栈中
最后我们将这棵树遍历完之后，栈中还有元素，如果栈中元素全为null,就说明这是一颗完全二叉树，否则不是。
这也依据完全二叉树的定义，如果从左往右开始编号，有一个子树漏掉了并且它的右边还有子树那就不是一颗完全二叉树

boolean isCompleteTree(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur==null){
                break;
            }
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        while(!queue.isEmpty()){
            TreeNode tmp =queue.peek();
            if(tmp!=null){
                return false;
            }
            queue.poll();
        }
        return true;
    }