树与二叉树介绍

树

树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：
（1）有且仅有一个特定的称为根的结点；
（2）当n>1时，其余结点可分为m（m>0）个互不相交的有限集T1、T2、...、Tm，其中每一个集合本身又是一棵树，并且称为根的子树
树的定义即采用递归方法，也就是在树的定义中还用到了树的概念，如下图的树中，根结点A具有两个子树T1和T2。

树
注：（1）n>0时根结点是唯一的，不可能存在多个根结点
（2）m>0时，子树的个数没有限制，但他们一定是互不相交的。
下图中的树不符合定义（相交）
不符合定义的树

结点分类：

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度。度为0的结点称为叶结点（Leaf）或终端结点；度不为0的结点称为非终端结点或者分支结点。除了根结点之外，分支结点也称为内部结点。树的度是树内各个结点的度的最大值。

结点分类

结点间关系：

结点的子树的根称为该结点的孩子（Child），相应地，该结点称为孩子的双亲（Parent）。同一个双亲的孩子之间互称为兄弟（Sibling）。结点的祖先是从根到该结点所经分支上的所有结点。所以对H结点来说，D、B、A都是它的祖先。反之，以某结点为根的子树中任一结点都称为该结点的子孙。B的子孙有D、G、H、I。
结点的层次（Level）从根开始定义，根为第一层，根的孩子为第二层。若某结点在第l层，则其子树的根就在l+1层。其双亲在同一层的结点互为堂兄弟。则D、E、F是堂兄弟，G、H、I、J也是堂兄弟。树中结点的最大层次称为树的深度（Depth）或者高度，下图中该树的深度为4。

结点间关系
如果将树中结点的各个子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则称为无序树。
森林（Forest）是m（m>=0）棵互不相交的树的集合。对于树中每个结点而言，其子树的集合即为森林。

线性表VS树：

线性结构：第一个数据元素无前驱，最后一个数据元素无后继，中间元素有一个前驱和一个后继
树结构：根结点无双亲且唯一，叶结点无孩子可以有多个，中间结点只有一个双亲，但可以有多个孩子

二叉树介绍

二叉树（Binary Tree）是n（n>=0）个结点的有限集合，该集合可能为空集（称为空二叉树），或者由一个根结点和两颗互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

特点：

（1）每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点
（2）左子树和右子树是有顺序的，次序不能任意颠倒
（3）即使树中某一结点只有一棵子树，也要区分它是左子树还是右子树**

五种基本形态：

（1）空二叉树
（2）只有一个根结点
（3）根结点只有左子树
（4）根结点只有右子树
（5）根结点既有左子树又有右子树
如下图所示：

树的五种形态

特殊二叉树：

（1）斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树，两者统称为斜树（树2和树5分别为左斜树和右斜树）。
（2）满二叉树：在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树（叶子只能出现在最下面一层，出现在其他层就不可能达成平衡，非叶子结点的度一定为2，在同样深度的二叉树中，满二叉树的结点个数最多，叶子个数最多）
（3）完全二叉树：对于一棵具有n个结点的二叉树按照层序编号，如果编号为i（1<=i<=n）结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树（按照层序编号，若出现空档，则说明不是完全二叉树）。

满二叉树和完全二叉树
满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。
完全二叉树特点：
（1）叶子结点只能出现在最下面两层
（2）最下层的叶子一定集中在左边连续位置
（3）倒数第二层若有叶子结点，则一定在右边连续位置
（4）如果结点度为1，则该结点只有左孩子，不存在只有右子树的情况
（5）同样结点树的二叉树，完全二叉树的深度最小

二叉树性质：

（1）在二叉树的第i层上至多有2i-1个结点（i>=1），至少有一个结点
（2）深度为k的二叉树至多有2k-1个结点（k>=1），至少有k个结点
（3）对于任何一棵二叉树T，如果其终端结点树为n0,度为2的结点数为n2，则n0=n2+1

完全二叉树性质：

（1）具有n个结点的完全二叉树的深度为[log2n]+1（[x]表示不大于x的最大整数）
（2）对于一棵有n个结点的完全二叉树（其深度为[log2n]+1）的结点按层序编号（从第一层到第[log2n]+1层，每层从左到右），对任一结点i（1<=i<=n）有：
a、如果i=1,则结点i是二叉树的根，无双亲；如果i>1，则其双亲为结点[i/2]
b、如果2i>n，则结点i无左孩子，即为叶子结点，否则其左孩子是结点2i
c、如果2i+1>n，则结点i无右孩子，否则其右孩子是结点2i+1

完全二叉树
如上图完全二叉树：
（1）i=1时，该结点就是根结点。i>1时，如结点i=7，其双亲为[7/2]=3,再比如结点i=9,其双亲为[9/2]=4
（2）对于结点i=6,2x6=12>10,故该结点无左孩子，即为叶子结点。对于结点i=5,2x5=10，正好为结点总数，故其左孩子为结点10
（3）对于结点i=5，2x5+1=11>10，所以没有右孩子。对于结点i=3，2x3+1=7<10,存在右孩子7