初识树

数据结构中有很多树的结构，其中包括二叉树、二叉搜索树、2-3树、红黑树等等。今天讲最简单的二叉树：

比较重要的相关术语

度（Degree）：一个节点拥有的子树数量就是节点的度。
叶子节点（Leaf）：度为0的节点。
深度：树中节点的最大层次

二叉树（BinaryTree）

二叉树是数据结构中一种重要的数据结构，也是树表家族最为基础的结构。
二叉树的定义：二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2i-1个结点；深度为k的二叉树至多有2k-1个结点；对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

image.png

满二叉树和完全二叉树：

满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值，所有叶子结点必须在同一层上。

满二叉树的性质：

1. 一颗树深度为h，最大层数为k，深度与最大层数相同，k=h;

2. 叶子数为2h;

3. 第k层的结点数是：2k-1;

4. 总结点数是：2k-1，且总节点数一定是奇数。

完全二叉树：若设二叉树的深度为h，除第 h 层外，其它各层 (1～(h-1)层) 的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树。

image.png

他们的 对应关系为一个满二叉树一定是一个完全二叉树，一个完全二叉树不一定是一个满二叉树。

二叉树的遍历

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

talk is cheap show me the code（少废话，放码过来）

定义一个二叉树

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;
    }
}

遍历方式

     /**
     * 前序遍历
     * */
    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());
    }

本文代码块引用 怀念小兔 代码。