树的基本概念
节点，根节点，父节点，子节点，兄弟节点都是属于树的范涛；
一棵树可以没有任何节点，称为空树；
一棵树可以只有1个节点，也就是只有根节点；
树又可以分为子树，左子树，右子树
节点的度（degree）：子树的个数
树的度：所有节点度中的最大值
叶子节点（leaf）：度为0的节点
非叶子节点：度不为0的节点
层数（level）：根节点在第1层，根节点的子节点在第2层，以此类推
节点的深度(depth);从根节点到当前节点的唯一路径上的节点总数
节点的高度（height）：从当前节点到最远叶子节点的路径上的节点总数
树的深度：所有节点深度中的最大值
树的高度：所有节点高度中的最大值
树的深度等于树的高度
按照顺序来分
有序树：树中任意节点的子节点之间有顺序关系
无序数：树中任意节点的子节点之间没有顺序关系
森林：由m（)棵互不相交的树组成的集合
二叉树
二叉树的表型的表现形势图如下所示：
二叉树的特点
每个节点的度最大为2，最小为0
左子树和右子树是有顺序的
即使某节点只有一棵子树，也要区分左右子树
二叉树的性质
非空二叉树的第i层，最多有个节点（i >= 1)
可以看出最多层最多有个节点是正确的
在高度为h的二叉树上最多有个结点（h>=1)
对于任何一棵非空二叉树，如果叶子节点个数为n0，度为2的节点个数为n2,则有：n0 = n2 + 1
证明：
1.假设度为1的节点个数为n1,那么二叉树的节点总数n = n0 + n1 + n2;
2.二叉树的边数T = n1 + 2 * n2 = n - 1 = n0 + n1 + n2 - 1
3.因此n0 = n2 + 1;
真二叉树(Proper Binary Tree)又称完满二叉树(Full Binary Tree)
真二叉树：所有节点的度要么为0，要么为2
满二叉树(Full Binary Tree)又称（Perfect Binary Tree)完美二叉树
所有节点的度要么为0，要么为2，且所有的叶子节点都在最后一层，如下图所示：
1.假设满二叉树的高度为h（h>=1),第i层的节点数量:,叶子节点数量：
,总节点数量n=
=
-------> h =
2.在同样高度的二叉树中，满二叉树的叶子节点数量最多，总结点数量最多
3.满二叉树一定是真二叉树，真二叉树不一定是满二叉树
完全二叉树(Complete Binary Tree)
叶子节点只会出现在最后2层，且最后1层的叶子节点都靠左对齐
完全二叉树从根节点至倒数第2层是一棵满二叉树，满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
如何判断是否为完全二叉树
判断条件：如果树为空，返回false，如果树不为空，开始层序遍历二叉树（用队列方式处理）
如果node.left != null && node.right != null,将node.left,node.right 按顺序入队；如果node.left == null && node.right != null ,返回false;如果node.left != null && node.right == null 或者 node.left == null && node.right == null ,那么后面遍历的节点应该都是叶子节点，否则返回false，遍历结束，返回true，代码图如下：
方法2相对方法1，减少重复代码的判断条件；
完全二叉树的性质
一棵有n个节点的完全二叉树(n>0),从上到下，从左到右对节点从0开始进行编号，对任意第i个节点，如果i = 0,它是根节点；如果i > 0,它的父节点编号为floor((i-1)/2);如果2i + 1 n - 1,它的左子节点编号为2i + 1;如果2i + 1 > n - 1,它无左子节点；如果2i+2
n -1,它的右子节点编号为2i + 2；如果2i + 2 > n - 1,它无右子节点；
测试题目
如果一棵完全二叉树有768个节点，求叶子节点的个数？
假设叶子节点个数为n0,度为1的节点个数为n1,度为2的节点个数为n2，那么总结点个数n = n0 + n1 + n2,另外二叉树的性质有一个定论n0 = n2 + 1;那么可以推导出n = 2n0 + n1 -1;另外完全二叉树的n1(子节点的个数）要么为0要么为1，所以这里分为两种情况：
1.n1为1的时候，n=2n0,n必然是偶数，那么叶子节点的个数n0 = n /2,非叶子节点个数n1+n2 = n/2
2.n1为0时，n = 2n0 -1,n必然是奇数，叶子节点个数n0=(n+1)/2,非叶子节点个数n1+n2=(n-1)/2
那么叶子节点个数n0 = floor((n+1)/2) = ceiling(n/2),非叶子节点个数n1 + n2 = floor(n/2) = ceiling((n-1)/2)
因此叶子节点个数为384
二叉树的遍历
遍历是数据结构中的常见操作，遍历有两种：1.正序遍历；2.逆序遍历
根据节点访问顺序的不同，二叉树常见的遍历方式有4种
1.前序遍历（Preorder Traversal)
2.中序遍历（Inorder Traversal）
3.后续遍历（Postorder Traversal）
4.层序遍历（Level Order Traversal）
前序遍历（Preorder Traversal）
下面的几种遍历顺序方法都以下面的图为准
访问顺序：根节点->前序遍历左子树->前序遍历右子树
7->4->2-1->3->5->9->8->11->10->12
中序遍历（Inorder Traversal）
访问顺序：左子树->根节点->右子树
1->2>3->4->5->7->8->9->10->11->12
可以看到二叉搜索树的中序遍历结果是升序的
后续遍历
访问顺序：左子树->右子树->根节点
1->3->2->5->4->8->10->12->11->9->7
层序遍历(Level Order Traversal)
访问顺序：从上到下，从左到右依次访问每一个节点
7->4->9->2->5->8->11->1->3->10->12
层序的遍历之路：使用队列
1.将根节点入队；2.循环执行以下操作，直到队列为空；3.将队头节点A出队，进行访问；4.将A的左子节点入队；5.将A的右子节点入队
遍历的作用
前序遍历：可以用于一些树状结构展示
中序遍历：二叉搜索树的中序遍历按升序或者降序处理节点
后续遍历：适用于一些先子后父的操作
层序遍历：计算二叉树的高度，判断一棵树是否为完全二叉树
前驱节点(predecessor)
前驱节点：中序遍历时的前一个节点，如果是二叉搜索树，前驱节点就是前一个比它小的节点
以图表说明一下：
前驱节点的寻找分几种情况的：
node.left != null
例如6,13,8;这种节点的前驱节点通常都是在node.left.right.right......,终止条件为right 等于 null，因为根据前面所说的，二叉搜索树，前驱节点就是前一个比它小的节点，如果left不等于null的情况下，那要符合这个条件，必须是节点在right.....一直到null结束寻找
6的前驱节点是5，因为6的做节点是5，5节点的right等于null，所以5就是前面一个比它小的节点；13的前驱节点是12，因为13的做节点是10，然后最终的有节点是12，12的right等于nul，所以12是最后一个右节点；8的前驱节点是7，因为7是8左节点之后的最后一个右节点；
node.left == null && node.parent != null
例如：7，11，9，1；类似这种节点node.left == null && node.parent != null的情况，前驱节点predecessor 是存放在node.parent.parent.....,最终的终止条件是node在parent的right右子树中，可以看到这种情况返回的前驱节点最终是node.parent....；
7的前驱节点是6，因为7的parent节点是6，7又是parent6的right节点，符合条件；11的前驱节点是10,首先11的parent节点是12，但是11不满足是node.parent的right，而是left，所以继续往上寻找，node=node.parent,这个时候node是12，那么12的parent节点是10，然后12又是parent10的right，所以返回node.parent,也就是10；9的前驱节点是8，分析和11的前驱节点以一样道理；1的前驱节点是null，也就是没有前驱节点，因为一路上去寻找的过程之后，发现并没有找到符合的条件
node.left == null && node.parent != null
符合这种情况的只有，没有左子树的跟节点
代码图大概如下：
后继节点（successor）
后继节点，中序遍历时的后一个节点，如果是二叉搜索树，后继节点就是后一个比它大的节点
以下图为例：
后继节点也要分几种情况：
node.right != null
例如1，8，4；这种节点的遍历条件是successor = node.right.left.left.left...，因为后继节点是后一个比它大的节点，对于搜索二叉树来说，所以首先要获取right的，然后再不断的获取left，获取到后一个比它大的节点，终止条件是left 为null；所以1的后继节点是2，因为2节点没有left节点；8的后继节点是9，因为8的right是10，10的left最后是9，9没有了left，所以9是最终的结束条件；4的后继节点是5，原理和8的分析一样
node.right == null && node.parent != null
例如：7，6，3，11；遍历条件是successor = node.parent.parent.parent...,终止条件是node在parent的左子树当中；因为只有在左子树当中，才能保证返回的node.parent 大于当前例子节点；所以7的后继节点是8，6的后继节点是7，3的后继节点4，11的后继节点是null
node.right == null && node.parent == null
满足这种条件的就只有没有右子树的根节点
代码图如下
二叉搜索树设计
private int size;//元素数量
private Node<E> root;//根节点
private Comparator<E>comparator;//比较器，根据不同的判断做不同的选择展示
public int size(); //返回树的元素个数
public boolean isEmpty;//查看树是否为空
public boolean clear();//清空树
public void add(E element);//添加元素
public void remove(E element);//移除元素
public boolean contains(E element);//是否包含元素
private Node<E>node(E element);//获取节点元素
在这里呢，只会介绍添加方法和删除方法；首先先看一下添加方法的步骤：
添加方法public void add(E element)
1.找到父节点；2.创建新节点；3.parent.left = node 或者parent.right = node;
4.如果值相等的元素的，覆盖旧元素
思路看上去还是比较简单易懂的，就是先判断是否是root元素，如果是root元素，直接赋值root元素，否则的话，就将传进来的element元素从root节点开始一个一个比较，找到符合项，然后插入元素，根据是左节点还是右节点插入相关位置
public void remove(Node node)
删除相对来说就会复杂点：因为要判断多个节点的情况：
1.两个节点的删除；1个节点的删除；叶子节点的删除
删除的操作以下面的图为例子说明一下：
删除度为2的节点
以下面的图为例，假设现在我要删除一个节点度为2的节点，假设是5，那么根据前面所说的
我们应该找到前驱后者后继节点的值覆盖原来节点的值，然后删除相应的前驱或者后继节点，那么删除5节点之后，应该变成如下图所示：
代码步骤分析图如下：
如果是度为2的节点，上面这一步就是在获取后继节点，然后将后继节点的值赋值给本来的node节点；也就是将后继节点6的值赋值给5，然后再用之前指向5的node节点指向6节点stepNode，方便之后的操作，如果不是度为2的节点，直接执行下面的操作就可以了，接下来看看node度为1和0的情况，
如果删除的节点是度为2的节点，就会多出上面一步操作删除度为2的步骤1，否则就直接进入到删除度为1或者0的步骤2。这里就直接针对度为2的来往下说，这个时候的node指向的是原来值为6的节点，那么这个节点的度就是为1，因为右节点为7，那么这个时候就要将replacementNode的parent指向6的parent，因为node是在parent的左边（也就是6在8的左边，所以将8的left指向7），也就是如下图：
于是通过这些步骤就得到来上面的删除度为2的节点图；
删除度为1的节点
遵循的原则应该是：用子节点替代原来节点的位置，child 是 node.left 或者child是node.right，如果用child替代node的位置，如果node是左子节点：child.parent = node.parent,node.parent.left = child;如果node是右子节点，child.parent = node.parent,node.parent.right = child
如果node是根节点：那么直接root = null，就可以了，也就是会进入if 判断中的这个node.parentNode == null；
非根节点：
假设现在删除4，根据前面说删除度为1的原则，首先拿到5节点作为child，也就是代码中的replaceNode，先将5节点的parent指向原来parent4的parent节点，也就是现在5节点的parent指向3节点，然后因为4节点是3节点的right，所以将3节点的right重新指向为child节点也就是5，所以得到图下：
删除叶子节点（也就是度为0的节点）
这种节点，如果是根节点的话，就直接node.parent = null,root = null即可，非根节点的话，就要判断是左或右子节点，如果node == node.parent.left --> node.parent.left = null ,如果node == node.parent.right--->node.parent.right = null
平衡二叉搜索树
为什么会有平衡二叉搜索树的概念出现呢？我们先来看看一个这样的情景：
如果是按照7，4，9，2，5，8，11的顺序添加节点：
另外一个是从小到大添加节点：
图一的复杂度是O(h) = O(logn),图二的复杂度是O(h) = O(n)
那么当n比较大的时候，两者的性能差异就会比较大，删除的过程之后也可能会导致图2的情况，这样就相当于二叉搜索树会退化成链表，这个会影响性能，因此我们需要平衡二叉树出现，首先因为节点的添加，删除顺序是无法限制的，因此我们可以在节点的添加，删除操作之后，想办法让二叉搜索树恢复平衡，也就是减少树的高度，但是调整的次数多的时候，反而会增加了时间复杂度，因此总的来说，我们要用尽量少的调整次数达到适度平衡。好啦，这个就是我目前学到的相关树的知识了，之后会学习AVL树，B树还有红黑树。
