二叉树

树的基础概念

节点：树中的每个元素被称为节点。
父子关系：相邻2个节点的连线，被称为父子关系。
叶子节点：没有子节点的节点。
父节点：指向子节点的节点。
子节点：被父节点指向的节点。
节点的高度：节点到叶子节点的最长路径（边数）
节点的深度：根节点到这个节点所经历的边的边数。
节点的层数：节点的深度+1。
树的高度：根节点的高度。

二叉树

每个节点最多有 2 个子节点，可能有一个子节点或一个子节点都没有。一个孩子都没有的节点就被称为叶子节点，叶子节点不能再生成新的枝杈。
二叉树具有唯一根节点，每个节点最多有一个父节点。
二叉树具有天然的递归结构。根节点的左子节点可以被看作一棵树，所以左子节点可以看成是这棵左子树的根节点。也就是说，每个节点的左子树也是二叉树，每个节点的右子树也是二叉树。

public class Node<E> {
    // 节点需要保存的元素
    E e;
    // 左子节点
    Node left;
    // 左子节点
    Node right;
}

满二叉树

有一种二叉树，除了叶子节点外，每个节点都有左右两个子节点。

完全二叉树

叶子节点在最后两层，并且最后一层的叶子节点靠左排列。除了最后一层，其它层的节点个数要达到最大。

二分搜索树

二分搜索树也是一棵二叉树，对于二分搜索树中的每个节点的值，都要大于左子树的所有节点的值，都要小于右子树的所有节点的值。
以上图为例，根节点的值是 28，左子树的节点的值是 16, 13, 22，满足小于 28 这个条件。
我们存储的元素必须要有可比较性。

二叉树的遍历

前序遍历：对于树中任意节点来说，先遍历当前节点，再递归调用左子节点，最后递归调用右子节点。
中序遍历：对于树中任意节点来说，先递归调用左子节点，再遍历当前节点，最后递归调用右子节点。
后序遍历：对于树中任意节点来说，先递归调用左子节点，再递归调用右子节点，最后遍历当前节点。

前序遍历代码：

// 二分搜索树的前序遍历
public void preOrder(){
    preOrder(root);
}
// 前序遍历以node为根的二分搜索树, 递归算法
private void preOrder(Node node){
    if(node == null)
    return;
    System.out.println(node.e);
    preOrder(node.left);
    preOrder(node.right);
}

中序遍历代码：

// 二分搜索树的中序遍历
public void inOrder(){
    inOrder(root);
}
// 中序遍历以node为根的二分搜索树, 递归算法
private void inOrder(Node node){
    if(node == null)
    return;
    inOrder(node.left);
    System.out.println(node.e);
    inOrder(node.right);
}

后序遍历代码：

// 二分搜索树的后序遍历
public void postOrder(){
    postOrder(root);
}
// 后序遍历以node为根的二分搜索树, 递归算法
private void postOrder(Node node){
    if(node == null)
    return;
    postOrder(node.left);
    postOrder(node.right);
    System.out.println(node.e);
}

层序遍历

一般使用非递归的队列方式实现。
由于队列的顺序是先进先出（先到先得），所以是从左到右进入队列。

public void levelOrder(){
    if(root == null)
    return;
    Queue<Node> q = new LinkedList<>();
    q.add(root);
    while(!q.isEmpty()){
        // 当前需要访问的元素，让它出队
        Node cur = q.remove();
        System.out.println(cur.e);
        // 让它的左右孩子节点入队
        if(cur.left != null)
        q.add(cur.left);
        if(cur.right != null)
        q.add(cur.right);
    }
}