重要 摘自：
https://zhuanlan.zhihu.com/p/24800009?refer=hinus
侵权删除
应用
- 数据库中索引是B+树
- 操作系统中的文件系统大多设计成树的结构
- JDK中的TreeMap是一种用树实现的Map，但是，它的实现是红黑树
定义
二叉树是一种树型结构
每个结点至多只有两棵子树
二叉树的子树有左右之分，其次序不能任意颠倒。
概念
- 节点
- 叶子节点，非叶子节点
- 树的高度
树中结点的最大层次称为树的高度，最后一层位于第二层，所以这棵树的高度就是 2
特点
- 在二叉树的第 i 层上至多有 2^{i - 1} 个结点。
- 深度为 k 的二叉树，最多有 2^k - 1 个结点。
- 这条性质由 1 可以直接得出：将每一层的最大结点数相加。这是一个公比为 2 的等比数列，其和为 2^k - 1
横向比较
-
满二叉树
除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。
如果一个二叉树，只有当第 k 层已经达到了 2^{k -1} 的最大值以后，才能往第 k + 1 层自左向右地添加结点
满二叉树.png 完全二叉树
除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐。
完全二叉树.png
- 完满二叉树
除了叶子结点之外的每一个结点都有两个孩子结点。
完满二叉树.png
- 二叉查找树
它的左孩子上的所有结点的值都比该结点小，而它的右孩子上的所有结点的值都比该结点大。
与该结点值相同的的结点可以放在左孩子上，也可以放在右孩子上，这个可以根据实际情况灵活实现。
结点定义
class Node {
public Object data;
public Node left;
public Node right;
}
创建二叉树
class Node {
public Object data;
public Node left;
public Node right;
public Node(Object d) {
this.data = d;
}
}
public class Main {
public static void main(String args[]) {
Node a = new Node(Integer.valueOf(1));
Node b = new Node(Integer.valueOf(2));
Node c = new Node(Integer.valueOf(3));
a.left = b;
a.right = c;
}
}
创建后的图像
image.png
树的节点
称 1 是父节点，2 是左孩子结点，3 是右孩子结点。
如果一个节点没有子结点，例如图中的 2 和 3 ，那这个节点也是叶子节点。
如果一个结点有子结点，也可以称其为内部结点，或者是非叶子结点。
树的高度
操作
- 二叉查找树
递进地判断待插入数据与树中结点值的大小关系，找到待插入数据应该出现的位置。
如果待插入数据比根结点的数据小，就去检查根结点的左孩子。如果左孩子不为空，就继续向下检查，如果左孩子为空，就说明已经找到应该插入数据的位置了。向右的情况则与向左的情况互为镜像，只是条件判断的符号换了一下而已。
class BinarySearchTree<T extends Comparable<T>> {
public Node root;
public boolean insert(T i) {
if (root == null) {
root = new Node(i);
return true;
}
Node current = root;
while (true) {
// 如果 i 比当前结点的值小
if (i.compareTo((T) current.data) < 0) {
if (current.left != null) {
current = current.left;
} else {
current.left = new Node(i);
break;
}
} else {
if (current.right != null)
current = current.right;
else {
current.right = new Node(i);
break;
}
}
}
return true;
}
}
