树与二叉树
1.树的定义与相关概念
树的示例：
树的集合形式定义
Tree=(K,R)
元素集合：K={ki|0<=i<=n,n>=0,ki∈ElemType}（n为树中结点数，n=0则树为空，n>0则为非空树）
对于一棵非空树，关系R满足下列条件：
1.有且仅有一个结点没有前驱，称为根结点。
2.处根结点外，其余每个结点有且仅有一个前驱。
3.每个结点（包括根），可以有任意多个（含0个）后继。
树的递归形式定义
树是由n(n>=0)个元素构成的有限集合。
任意一颗非空树，都满足：
1.有且仅有一个根节点。
2.其余结点被分成m(m>=0)个
3.互不相交的有限集T1,T2,...Tm,其中每一个集合Ti(1<=i<=m)又是一颗树（递归），称为根的子树。
树结构反映了元素间的层次关系，分类分级的问题都可以考虑用树来描述。
树的基本术语——1
结点的度：结点所拥有的子树的个数。
树的度：树中所有结点的度的最大值。
叶结点：度为零的结点。
分支结点：度不为零的结点。
孩子结点和双亲结点：在一颗树中，每个结点的后继，被称为该结点的孩子结点，相应地，该结点被称为孩子结点地双亲结点。
兄弟结点：具有同一双亲的孩子结点。
树的基本术语——2
结点的祖先：从根到该结点所经分支上的所有结点都称为该结点的祖先。
结点的子孙：以某节点为根的子树中的任一结点。
结点的层次：树是一种层次结构，树中的每个结点都处于某个层次上。
树的深度：树中所有结点层次的最大值，也成为树的高度。
树的基本术语——3
有序树：树中的各结点的子树是按照从左到右有序排序的，即各子树的位置不能交换。
无序树：树中各结点的子树排序是无序的。
森林：m(>=0)颗互不相交的树的集合。
2.二叉树的定义
二叉树：每个结点最多有两棵子树的有序树
二叉树或者是一棵空树，或者是一棵由一个根节点和两棵互不相交的分别称做根的左子树和右子树组成的非空树，左子树和右子树同样是一颗二叉树。
注意：
二叉树的度只能是0、1或2；
二叉树是有序树，它的左、右子树是有次序的，即使只有一棵子树也要区分是左子树还是右子树。
3.满二叉树与完全二叉树
满二叉树：二叉树的所有分支结点都有左子树和右子树，并且所有叶子结点都在二叉树的最下一层。
完全二叉树：具有n个结点的完全二叉树，它的结构与满二叉树的前n个结点的结构相同。
4.二叉树的性质
性质1：非空二叉树上的叶结点数等于双分支结点数加1.即：n0=n2+1
证明：
设n0,n1,n2分别代表度为0,1,2的结点的个数，则结点总数n=n0+n1+n2
除根结点以外，每个结点上层都有一个分支与之相连，因此，具有n个结点的二叉树的额分支总数为B=n-1
这些分支来自度为1和度为2的结点，因此，分支总数B=n1+2n2
由上述三个式子得出：n0=n2+1
性质2：非空二叉树的第i(i>=1)层上最多有2的i-1次方个结点。
性质3：深度为h(h>=1)的非空二叉树最多有2的h次方-1个结点
性质4：具有n(n>0)个结点的完全二叉树的深度：h=[log2的n次方]+1
性质5：n个结点的完全二叉树，按从上至下，从左至右的次序对结点编号，则编号为i的结点有以下性质：
1、若编号为i的结点满足：i<=[n/2],即2i<=n.则该结点为分支结点，否则为叶子结点。
2、若n为奇数，则每个分支结点既有左孩子又有右孩子；
3、若n为偶数，则编号最大的分支结点（编号为n/2）只有左孩子，没有右孩子，其余分支结点都有左、右孩子。
示例：已知一棵完全二叉树的第6层有7个结点，则：
前5层为满二叉树，共有结点2的5次方-1=31，第6层7个结点，总结点数为31+7=38.
由于完全二叉树最后一层的结点必须从左至右连续出现，所以 第6层的7个结点中，只有最后一个结点的双亲是度为1的结点，即度为1的结点有1个。
5.二叉树的顺序存储结构
在一组连续的存储单元中，按照完全二叉树中结点编号将结点自上而下、自左至右的顺序存储。
元素的位置序号和结点的编号相对应，即结点在数组中的位置表示了结点之间的关系：
1、结点编号为i，则：
2、结点i的双亲结点[i/2]
3、结点i的左子结点2i，右子结点2i+1
非完全二叉树 的存储方法：
6.二叉树的链式存储结构
二叉树结点类型：
typedfe struct node{
ElemType data;//数据域
struct node *left;
struct node *right;//结点的左右子树指针
}BTNode;//二叉树结点类型一个二叉链表由根指针root唯一确定。
若二叉树为空，则root=NULL；
若结点的某个孩子不存在，则相应的指针为空。
三叉链表：根据实际问题的需要，还可以在结点中添加父结点的指针。
7.逻辑关系与存储结构
