这里介绍的都是关于树的基础概念，用以参考，防止发生概念混淆。
1）树的结点
树的结点是由一个数据元素及关联其子树的边所组成，上图中的a图是只有一个结点的树，b图是拥有三个结点的树。
2）结点的路径
结点的路径是指从根节点到该节点所经历的结点和分支的顺序排列。比如上图中c图中H结点的路径是：A-->C-->H。
3）路径的长度
路径的长度是指结点路径中所包含的分支数。比如c图中H结点的路径长度是2。因为A是根节点不计数，C、H两个含有分支的结点计数。
4）结点的度
结点的度是指该结点所拥有子树的数目。例如c图中A的度为3，B的度为2，C的度为3。
5）树的度
树的度指的是树中所有结点的度的最大值。注意这个值并不是指根的度，而是指所有结点度的最大值。比如上图c中树的度是3。
6）叶结点（终端结点）
叶结点是指树中度为0的结点，叶结点也叫终端结点。比如c图中的E、F、G、H、I都是叶结点。
7）分支结点（非终端结点）
分支结点是指树中度不为0的结点，分支结点也称为非终端结点。树中除了叶结点之外都是分支结点。
8）子结点（孩子结点）
一个结点的子结点是指这个结点的子树的根节点。上图c中，A的子结点是B、C、D。
9）父结点（双亲结点）
一个结点的父结点是指：若树中某个就结点有子结点，则这个结点就称为其子结点的父结点。比如c图中A是B、C、D的父结点。
10）子孙结点
一个结点的子孙结点是指这个结点的所有子树中的任意结点。如c图中A的子孙结点是B、C、D、E、F、G、H、I。
11）祖先结点
一个结点的祖先结点是指该结点的路径中除此节点以外的所有结点。比如c图中G的祖先结点是A、C。
12）兄弟结点
兄弟结点是指具有同一双亲的结点。比如c图中B、C、D都是A的子结点，所以B、C、D拥有共同的双亲，所以B、C、D是兄弟结点。
13）结点的层次
规定树中根结点的层次为0，则其他结点的层次是其父结点的层次加1。比如c图中G的层次是2。
14）树的深度
树的深度是指树中所有结点的层次树的最大值加1。这个值和树的度有些类似，5）中描述了树的度。他们是两个完全不同的概念。c图中国树的深度是3。
15）有序树
有序数是指树中各结点的所有子树之间从左到右有严格的次序关系，不能互换。也就是说，如果子树的次序不同则对应着不同的有序树。常说的二叉树就是一种有序树。
16）无序树
与有序树相反，无序树是指树中各结点的所有子树之间没有严格的次序关系。按前面树的定义可知，树是无序树，即树中的所有结点从左到右没有次序之分，其次序可以任意颠倒。
17）森林
森林是指由m（m>=0）棵互不相交的树所构成的集合。如上图中a、b、c三棵树可以构成一个森林。

1）性质1：**二叉树中**第i（i>=0）层上的结点数最多为 2^i^ 个。
2）性质2：深度为h的**二叉树**最多有 2^h^-1 个结点（因为根节点只有一个，所以是 2^h^-1）。
3）性质3：对于任何一棵**二叉树**，若其叶子节点个数为n，度为2的结点个数为h。则有h+1 = n。(观察满二叉树的结构很容易看出来)
4）性质4：具有n个结点的**完全二叉树**，结点数为奇数时其深度为log~2~n ，结点数为偶数时为 log~2~(n+1) 。（根据性质1和性质2不难推导出）
5）性质5：具有n个结点的**完全二叉树**，若从根节点开始从上到下按照层次关系从左到右从0开始对所有结点进行编号，则对于任意一个编号为 i（0<= i < n） 的结点有：
  ①若i=0，则编号为i的结点是二叉树的根节点，它没有双亲；若i>1,则编号为i的结点其双亲的编号为(i-1)/2。（观察满二叉树易于理解）
  ②若2i+1>=n，则编号为i的结点无左孩子，否则编号为2i+1的结点就是其左孩子。（结合性质1和性质2，观察完全二叉树易于理解）
  ③若2i+2>=n，则编号为i的结点无右孩子，否则编号为2i+2的结点就是其右孩子。（②中的公式：2i+1>=n加1自然就是右结点了的描述了）

1）二叉树的顺序存储结构
二叉树的存储实现方法有很多种，但归纳起来主要分为顺序存储和链式存储两大类。
二叉树的顺序存储是指按照某种顺序依次将二叉树中的各个结点值存放在一组地址连续的存储单元中。由于二叉树是非线性结构的，所以需要将二叉树的各个结点按照一定的次序排列成线性序列，再通过这些结点在线性序列中的相对位置，确定二叉树中的各个结点之间的逻辑关系。由二叉树的性质5可知，对于一棵**完全二叉树**，可以从根节点开始自上而下并按照层次从左到右对结点进行依次编号，然后根据编号顺序将其存放在一维数组中，其结点之间的逻辑关系可由性质5中父结点与子结点编号之间的关系式计算得到。
上面所说是对于完全二叉树，那么**非完全二叉树**该怎么使用线性结构来表示呢？对于非完全二叉树通常的做法都是在树中增加一些虚结点，使其成为完全二叉树，剩下的处理就与完全二叉树相同了，只不过在数据存储在数组是上时，虚节点对应的位置不存放任何值。
**对于满二叉树和完全二叉树，顺序存储是一种最简单、最节省空间的存储方式，而且能使操作简单，所以顺序存储方式非常适合用于满二叉树和完全二叉树**。对于非完全二叉树来说由于有虚结点的存在会造成空间浪费，对于有n个结点的右支树来说，他的深度是n，就会有2^n^-1个结点被分配，但只存储了n个结点，空间上是一种极大的浪费。
2）二叉树的链式存储结构
二叉树的链式存储结构是指将二叉树的结点随机存放在位置任意的内存空间中，各个结点之间的逻辑关系通过指针来反应。因为任意二叉  树的结点最多会有一个父结点，两个子结点。所以二叉树的链式存储结构又划分为了**二叉链表存储结构**和**三叉链表存储结构**。
  ①二叉链表存储结构
  在二叉链表存储结构中，二叉树的每个结点设置有三个域：数据域、左孩子域、右孩子域，其中数据域用来存储该结点的数据，左、右孩子用来存放指向左、右孩子结点的指针。
  ②三叉链表存储结构
  三叉链表存储结构是指在二叉链表的结点结构中增加一个父结点域，用以存放指向父结点的指针。
3）总结
顺序存储结构适合满二叉树和完全二叉树只在非完全二叉树时比较浪费空间，三叉链表存储结构在访问父结点和子结点时特别方便但是空间开销较大，在实际中二叉树的实现最多的还是二叉链表存储结构，可以认为这是一种折中的方案，空间上节省介于顺序存储结构与三叉链表存储结构之间。下面展示下二叉链表存储结构的结点类的实现：

//递归遍历二叉树：先根遍历
    public void preRootTraverse(BiTreeNode node){
        if(node != null){
            System.out.println(node.data);
            preRootTraverse(node.leftChild);
            preRootTraverse(node.rightChild);
        }
    }
    //递归遍历二叉树：中根遍历
    public void inRootTraverse(BiTreeNode node){
        if(node != null){
            preRootTraverse(node.leftChild);
            System.out.println(node.data);
            preRootTraverse(node.rightChild);
        }
    }
    //递归遍历二叉树：后根遍历
    public void afterRootTraverse(BiTreeNode node){
        if(node != null){
            preRootTraverse(node.leftChild);
            preRootTraverse(node.rightChild);
            System.out.println(node.data);
        }
    }

//非递归便利二叉树：先根遍历
    //根据书中提供的两次循环改进而来，这里只需要一次循环就可以实现二叉树的遍历，
    // 其实本质上差别不大,时间复杂度其实是一样的
    /**
     * 思路：
     * 第一步：将根节点放入到栈中。
     * 第二步：然后不断遍历左节点并输出，当前结点有右结点就放入栈，有左节点就继续遍历
     * 第四步：全部遍历完成后，退出循环
     *
     * @param node
     * @throws Exception
     */
    public static void inRootTraverseMy(BiTreeNode node) throws Exception{
        if(node != null){
            IStack stack = new LinkedStack();
            stack.push(node);
            if(!stack.isEmpty()){
                BiTreeNode popNode = (BiTreeNode)stack.pop();
                while(popNode.data!=null){
                    System.out.println(popNode.data);
                    if(popNode.rightChild!=null){
                        stack.push(popNode.rightChild);
                    }
                    if(popNode.leftChild!=null){
                        popNode = popNode.leftChild;
                        continue;
                    }
                    popNode = stack.isEmpty()?new BiTreeNode():(BiTreeNode)stack.pop();
                }
            }
        }
    }

/**
     * 思路：
     * 第一步：先将根节点放入栈中，然后依次往下遍历左节点，将其全部放入栈中
     * 第二步：第一步完成后，取出栈顶结点，此时栈顶结点应该是最左下次的结点。
     * 第三步：循环输出结点，第二步取出的结点不为空则进入循环，因为是最左节点，不为空可直接输出，
     *         然后判断是否拥有右节点，有的话，从新从第一步走。没有右节点的话则可以直接向上遍历结点。
     *
     * @param node
     * @throws Exception
     */
    public static void inRootTraverseNew(BiTreeNode node) throws Exception{
        if(node != null){
            IStack stack = new LinkedStack();
            stack.push(node);
            while(!stack.isEmpty()){
                while(((BiTreeNode)stack.peek()).leftChild!=null){
                    stack.push(((BiTreeNode)stack.peek()).leftChild);
                }
                while(!stack.isEmpty()){
                BiTreeNode nodePop = (BiTreeNode)stack.pop();
                    if(nodePop.data!=null){
                        System.out.println(nodePop.data);
                    }
                    if(nodePop.rightChild!=null){
                        stack.push(nodePop.rightChild);
                        break;
                    }
                }
            }
        }
    }