树：是一种一对多的数据结构，采用链式存储，是n个结点的有限集，如果n=0则是一个空树，任意一个非空树只有一个根节点。
其中，A为根(root)，A,B,D…称为结点：
节点包含了值和一些信息，有两种表示方法，其中孩子表示法用的较多
树的遍历：以上图为例
- 前序遍历：根节点->左子树->右子树 A B D C E F
- 中序遍历：左子树->根节点->右子树 D B A E C F
- 后序遍历：左子树->右子树->根节点 D B E F C A
- 层序遍历：从左到右，一层一层走完整个树 A B C D E F
> //前序遍历
> void perOrder(TreeNode root){
> if(root==null){
> return;
> }
> System.out.print(root.val+"");
> perOrder(root.left);
> perOrder(root.right);
> }
> //中序遍历
> void midOrder(TreeNode root){
> if(root==null){
> return;
> }
> midOrder(root.left);
> System.out.print(root.val+" ");
> midOrder(root.right);
> }
> //后序遍历
> void postOrder(TreeNode root){
> if(root==null){
> return;
> }
> postOrder(root.left);
> postOrder(root.right);
> System.out.print(root.val+" ");
> }
> //层序遍历借助队列完成
> public void leveOrder(TreeNode root){
>
> Queue queue=new LinkedList<>();
>
> if(root!=null){
> 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);
> }
> }
>
> }
>
2：二叉树
二叉树：二叉树是n (n>=0) 个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的，分别称为根节点的左子树和右子树的二叉树组成。
二叉树的一些特征：
- 若规定根节点的层数为1，则一颗非空二叉树的第i层上最多节点个数为 2 i − 1 ( i > 0 ) 2^{i-1}(i>0) 2i−1(i>0)
- 若规定只有根节点的二叉树的深度为1，则深度为k的二叉树最大结点数为 2 k − 1 ( k ≥ 0 ) 2^k-1(kgeq0) 2k−1(k≥0)
- 对任何一个二叉树，如果叶节点的个数为 n 0 n_0 n0，度为2的非叶结点个数为 n 2 n_2 n2，则有 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
- 具有n个结点的完全二叉树的深度k为 k = l o g 2 n + 1 ( 向 上 取 整 ) k=log_2^{n+1}(向上取整) k=log2n+1(向上取整)
- 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的节点有：
- 若 i > 0 i>0 i>0，双亲序号： ( i − 1 ) / 2 (i-1)/2 (i−1)/2，若 i = 0 i=0 i=0，i为根节点编号，无双亲结点
- 若 2 i + 1 < n 2i+1
- 若 2 i + 2 < n 2i+2
3：完全二叉树完全二叉树：对于一棵具有n个结点的二叉树按层序编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这颗二叉树称为完全二叉树。完全二叉树在缺失时，只能缺失右结点。
判断当前二叉树是不是完全二叉树：
借助队列完成判断，从根节点出发，入队，队列不为空则出队列，并判断该结点有没有左右孩子，有则放进队列，直到出队列的元素为null，跳出循环。再判断队列中的元素是否都为null，都为null则是完全二叉树。
//判断当前树是不是完全二叉树
boolean isCompleteTree(TreeNode root){
int size=0;
Queue queue=new LinkedList<>();
if(root!=null){
queue.offer(root);
size++;
}
while (! queue.isEmpty()){
TreeNode cur = queue.poll();
if(cur!=null){
queue.offer(cur.left);
size++;
queue.offer(cur.right);
size++;
}else {
break;
}
}
while (!queue.isEmpty()){
TreeNode cur=queue.peek();
if(cur!=null){
return false;
}else {
queue.poll();
}
}
return true;
}
