数据结构：二叉树

重要 摘自：
https://zhuanlan.zhihu.com/p/24800009?refer=hinus
侵权删除

应用

• 数据库中索引是B+树
• 操作系统中的文件系统大多设计成树的结构
• JDK中的TreeMap是一种用树实现的Map，但是，它的实现是红黑树

定义

二叉树是一种树型结构
每个结点至多只有两棵子树
二叉树的子树有左右之分，其次序不能任意颠倒。

概念

• 节点
• 叶子节点，非叶子节点
• 树的高度

树中结点的最大层次称为树的高度，最后一层位于第二层，所以这棵树的高度就是 2

特点

• 在二叉树的第 i 层上至多有 2^{i - 1} 个结点。
• 深度为 k 的二叉树，最多有 2^k - 1 个结点。
  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;
    }
}