树

这篇文章主要记录对树（Tree）这种数据结构的学习。首先是定义，懒人直接复制粘贴百度百科的，当然我也有仔细看过：

定义

树是一种数据结构，它是由n（n>=1）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；

多扯一句，不相交的意思就是不能出现环，如果出现了，那就变成了图（Graph），散列表（HashMap）在jdk1.8之前用拉链法实现的时候，由于HashMap不是线程安全的，如果出现多线程put的情况，最坏的结果就是出现环，这会导致在遍历时死循环。

比较重要的相关术语

度（Degree）：一个节点拥有的子树数量就是节点的度。
叶子节点（Leaf）：度为0的节点。
深度：树中节点的最大层次。
嗯，术语就记这三个了，什么父子节点、双亲节点、祖先、子孙我觉得都没有记录的必要，森林这个名词还是挺有意思的。

二叉树（BinaryTree）

二叉树就是每个节点最多有两个子节点的树，二叉树非常有用，必须要好好掌握。二叉树的数学性质暂不在此记录，百度百科都有，需要时再去查阅。

满二叉树

每个非叶子节点都有左右节点且叶子节点全在二叉树的最底层的二叉树叫做满二叉树。满二叉树画出来一定是三角形。

完全二叉树

把满二叉树的节点按照从下往上从右往左的方向抹除，剩下的就是完全二叉树。也就是说，满二叉树的每个节点要么是叶子，要么有左右子节点，要么只有左子节点。

二叉树的遍历

二叉树的遍历分前序遍历（DLR）、中序遍历（LDR）、后序遍历（LRD）。对于二叉树的每个节点而言，遍历都有三个对象，分别是本身、左子、右子，而所谓的前中后，指的就是本身在遍历中的位置，所以前序遍历就是先访问本身，再左右子，中序遍历就是先左子再本身再右子，后序则是先左右子再本身。
关于缩写，我是比较好奇的，D（Degree）L（left child）R（right child）查阅到的英文是这样，暂时这么记。

代码实现（存储结构）

理论上是可以用数组或者链式结构实现，但我觉得数组的实现仅仅应该存在于理论中，数组实现，无非就是定义一种数据结构，它包含左右子树的索引和数据，相比链式结构没有任何灵活性可言，又必须连续存储。所以这里我只用链式结构实现。

public class BTreeNode<E> {
    E data;
    BTreeNode<E> left;
    BTreeNode<E> right;

    public BTreeNode(E data, BTreeNode<E> left, BTreeNode<E> right) {
        this.data = data;
        this.left = left;
        this.right = right;
    }
}

以上，我只定义了节点这个类，为什么不定义二叉树而是只定义节点呢？因为目前我还没有深入研究二叉树的作用，讲真，只写出一颗死的二叉树完全不需要定义一个连方法都没有的二叉树类，而基于println的三种遍历实际上没有任何意义，也不应该是二叉树这个类的方法，它应该是静态的工具方法。以下是遍历的代码：

    /**
     * 前序遍历
     * */
    public static <E> void dlrTraverse(BTreeNode<E> root){
        if(root == null)
            return;
        println(root.data.toString());
        dlrTraverse(root.left);
        dlrTraverse(root.right);
    }
    /**
     * 中序遍历
     * */
    public static <E> void ldrTraverse(BTreeNode<E> root){
        if(root == null)
            return;
        ldrTraverse(root.left);
        println(root.data.toString());
        ldrTraverse(root.right);
    }
    /**
     * 后序遍历
     * */
    public static <E> void lrdTraverse(BTreeNode<E> root){
        if(root == null)
            return;
        lrdTraverse(root.left);
        lrdTraverse(root.right);
        println(root.data.toString());
    }