二叉树
满二叉树：除了叶子节点之外，每个节点都有左右两个子节点。
完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大。
二叉树高度计算：
第一种是深度优先思想的递归，分别求左右子树的高度。当前节点的高度就是左右子树中较大的那个+1；
第二种可以采用层次遍历的方式，每一层记录都记录下当前队列的长度，这个是队尾，每一层队头从0开始。然后每遍历一个元素，队头下标+1。直到队头下标等于队尾下标。这个时候表示当前层遍历完成。每一层刚开始遍历的时候，树的高度+1。最后队列为空，就能得到树的高度。
链式存储法
顺序存储法若该节点位置为i，则左子树位置为（2i），右子树位置(2i+1)，父节点为(i/2)向下取整。
非完全二叉树的存储会浪费空间
前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。
中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。
后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。
前序遍历的递推公式：
preOrder(r) = print r-->preOrder(r->left)->preOrder(r->right)
中序遍历的递推公式：
inOrder(r) = inOrder(r->left)->print r->inOrder(r->right)
后序遍历的递推公式：
postOrder(r) = postOrder(r->left)->postOrder(r->right)->print r
遍历的时间复杂度是O(n)，每个节点都可能会被访问两次。
二叉查找树：
在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。
查找
public Node find(int data) {
Node p = tree;
while (p != null) {
if (data < p.data) p = p.left;
else if (data > p.data) p = p.right;
else return p;
}
return null;
}
插入
public void insert(int data){
if(tree == null){
tree = new Node(data);
return;
}
Node p = tree;
while(p != null){
if(data>p.data){
if(p.right == null){
p.right = new Node(data);
return;
}
p = p.right;
}else{
if(p.left == null){
p.left = new Node(data);
return;
}
p = p.left;
}
}
}
删除
1.如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。
2.如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。
3.如果要删除的节点有两个子节点，我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。
public void delete(int data){
Node p = tree;//初始化节点指向根节点
Node pp = null;
while(p != null && p.data != data){
pp = p;
if(data>p.data) {
p = p.right;
}else{
p = p.left;
}
}
if(p == null){
return;//没有找到
}
//删除的有两个子节点
if(p.left != null && p.right != null){//p是当前要删除的节点
Node minP = p.right;
Node minPP = p; //minPP 表示minP的父节点
while(minP.left!=null){//找到要删除节点的右子树的最小值
minPP = minP;
minP = minP.left;
}
p.data = minP.data;//找到了最小值
p = minP;//指向p的Node指针指到minP
pp = minPP;//指向pp的Node指针知道minPP
}
//删除节点是叶子节点或者仅有一个子节点
Node child; //p的子节点
if(p.left != null){
child = p.left;
}else if(p.right != null){
child = p.right;
}else {
child = null;
}
if(pp == null){
tree = child;//删除的是根节点
}else if(pp.left == p){
pp.left = child;//删除
}else{
pp.right = child;//删除
}
}
满二叉树 完全二叉树 平衡二叉查找树 插入删除查找的时间复杂度是O(logn)。
二叉树比散列表优势的分析：
1.散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
2.散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
3.笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
4.散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。