数据结构：树与二叉树
1、树的基本概念
1.1树的定义
树是n个结点的有限集。
若n=0，称为空树；若n>0称为非空树，非空树有且仅有一个称之为根的结点。
除根结点以外的其余结点可分成m个互不相交的有限集T1,T2,......Tm,每个有限集合本身又是一棵树，并且称为根的子树。
我们可以根据下面这张图来理解。
根结点：非空树中无前驱结点的结点。图中A就是根结点
结点的度：结点拥有的子树。例如A结点拥有三棵子树，所以它的度为3
深度：树种结点的最大层次，图中的树深度为4
接下来我们介绍各个结点之间的关系：
叶子：也是终端结点，即没有子树的结点
孩子与双亲：一个结点伸出的子树之间的关系
堂/兄弟：同一层次结点的关系
（树的概念可以类比族谱，这样更容易理解）
1.2树的基本术语
树可以分成有序树和无序树：
有序树指的是结点各子树从左至右有序不能互换（例如：二叉树）
无序树中各结点子树可以互换位置。
学习了树的基本知识，下面就引出森林的概念：
如图所示，这是一个再正常不过的树，A是根结点，T1,T2,T3是它的子树。这时如果我们把A结点和B,C,D结点的连接断开，变成下面这个样子，就称为森林：
此时，B,C,D是三棵相互独立的树。
这就是森林，即m棵互不相交的树的集合。
1.3树的其他表示方式
树所包含的逻辑结构还可以用广义表，嵌套集合等形式表示，大家根据图片就可理解。
2、二叉树的基本知识
2.1二叉树的概念
二叉树是一种特殊的树，它只有左子树和右子树。其基本特点如下：
1、结点的度小于等于2
2、是有序树（子树有序，不能颠倒）
我们来看一个例子：具有三个结点的二叉树可能有几种不同形态，普通树呢？
二叉树由于子树有序不能颠倒，所以共有5种形态：
而普通的树是无序的，只用考虑层次，顾只有两种：
2.2二叉树的性质
我们首先介绍两种特殊的二叉树
1、满二叉树：
如图就是一个满二叉树，它具有以下特点：
每层结点数都是最大结点数（每层都满）
叶子结点全部在最底层
每一结点位置都有元素
综上，我们可以很轻松地给出结论，一棵深度为k的满二叉树，它的共有个结点。
2、完全二叉树：
我们设完全二叉树有k层，当k-1层是满二叉树，只有最后一层叶子不满，且全部集中在左边时即称为完全二叉树，如图所示：
那么我们再来辨析以下下面呢几棵树哪个是完全二叉树：
我们给出结果，图1是满二叉树，图三是完全二叉树，其余的都不是。
下面我们介绍二叉树最重要的4条性质：
性质1：在二叉树的第i层至多有个结点
我们可以这样理解：
性质2：深度为k的二叉树至多有 个结点
同样，这是一个等比数列求和的问题，第一行为，第二行
，如此类推，最终求和结果就是
性质3：对任意一棵二叉树，如果终端结点数（叶子结点）为0，度为2的结点数为n2，则n0=n2+1
性质4：具有n个节点的完全二叉树深度为⌈log2(n+1)⌉或⌊log2n⌋+1
也可以这样理解-1<n<
-1