java二叉树

      在正式讲解之前先给大家普及一些知识，首先二叉树仅仅是数的一种情况由于它具有的一些性质十分适合对树进行研究因此我们主要通过二叉树来讲解数，其次二叉树的学习并没有大家想象的那么难，虽然二叉树中有许多实现步骤都用到了递归，但实际单独并不高，如果大家认真学习二叉树大家对递归的认识也会更上一层楼。

    下面开始对二叉树的讲解：

      二叉树（Binary Tree）是计算机科学中一种重要的数据结构，每个节点至多有两棵子树，且子树有左、右之分，这种结构使得二叉树非常适合进行高效的查找操作。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称作根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。如图：

注意：树形结构中子树之间不能有交集，否则就不是树结构

在这里我们还需要普及一下树中的一些相关定义，对后续的学习同样十分重要：

结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为6
树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为6
叶子结点或终端结点：度为0的结点称为叶结点； 如上图：B、C、H、I...等节点为叶结点
双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点
孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点
根结点：一棵树中，没有双亲结点的结点；如上图：A
结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推

树的高度或深度：树中结点的最大层次； 如上图：树的高度为4
树的以下概念只需了解，在看书时只要知道是什么意思即可：
非终端结点或分支结点：度不为0的结点； 如上图：D、E、F、G...等节点为分支结点
兄弟结点：具有相同父结点的结点互称为兄弟结点； 如上图：B、C是兄弟结点
堂兄弟结点：双亲在同一层的结点互为堂兄弟；如上图：H、I互为兄弟结点
结点的祖先：从根到该结点所经分支上的所有结点；如上图：A是所有结点的祖先
子孙：以某结点为根的子树中任一结点都称为该结点的子孙。如上图：所有结点都是A的子孙
森林：由m（m>=0）棵互不相交的树组成的集合称为森林。

需要特别注意的是：

一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

     二叉树中也有一些特殊的树 分别为：完全二叉树和满二叉树。

 满二叉树：顾名思义就是装满了的二叉树，二叉树的每一层节点都装满，假设二叉树有n层那么这个满二叉树的结点数就是2^n-1;如图：

完全二叉树： 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。

如图：

二叉树的性质：

   1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有
(i>0)个结点
   2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是
(k>=0)
   3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1
   4. 具有n个结点的完全二叉树的深度k为
上取整
   5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i
的结点有：
  若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，无双亲结点
  若2i+1<n，左孩子序号：2i+1，否则无左孩子
  若2i+2<n，右孩子序号：2i+2，否则无右孩子 

   二叉树的遍历：前序，中序，后序和层序遍历。

   在这三种遍历方法中前序，中序和后序遍历的思路是一样的。

   这里的前中后指的是根节点，意思就是根节点的输出顺序。

   在这里我们讲解前三种遍历的递归方法，思路图如下：

从根节点1出发先左递归在向右递归，根据自己的想法也就是前中后的顺序来进行想要的输出顺序。 

  前序遍历结果：1 2 3 4 5 6
  中序遍历结果：3 2 1 5 4 6
  后序遍历结果：3 1 5 6 4 1