数据结构三之树
一丶树的相关概念
1-1丶树的定义
树是n(n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：
- 1.有且仅有一个特定的结点称为跟结点。
- 2)当n>1时，其余结点可以分m(m>0)个互不相交的有限集T1，T2，，，，Tm，其中每个集合本身又是一棵树，并且称为跟的子树。
树
1-2丶结点的度
结点拥有的子树的个数称为结点的度。度为0的结点称之为叶子结点或者终端结点。度不为0的结点称之为非叶子结点或者非终端结点。除根结点外，分支结点也称为内部结点。
树的度就是树内各结点的度的最大值。
结点的度
1-3丶层次和深度
结点的层次从跟结点开始定义，根为第一层，根的孩子结点为第二次。若某结点在第l层，其孩子结点在第l+1层。其双亲在同一层的结点互为堂兄弟。如下如所示,D，E，F互为堂兄弟，而G，H，I，J也是。
树的最大层次为称为树的深度或高度，当前树的高度为4。
层次和深度
1-4丶有序树和无序树
如果将树中结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树。否则就是无序树。
1-5丶森林
森林是m（m>=0）颗互不相交的树的集合。
二丶树的存储结构
简单的顺序存储不能满足树的存储要求。需要结合顺序存储和链式存储来实现树的存储。
树有三种表示法
- 双亲表示法
- 孩子表示法
- 孩子兄弟表示法
2-1丶双亲表示法
在每一个结点中，附设一个指示器指示其双亲结点到链表的位置。
双亲表示法
2-2丶孩子表示法
如图所示
孩子表示法方案一
孩子表示法方案二
2-3丶孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果是存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟，依次来表示一棵树。如图所示
孩子兄弟表示法
比较好的方案
把每一个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子单链表，如果是叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中。
比较好的方案
三丶二叉树
二叉树是n个结点的有限集合，该集合或者为空集(称为空二叉树)，或者由一个根结点和两颗互不相交的，分别称为跟结点的左子树和右子树的二叉树组成。
二叉树
3-1丶特殊的二叉树
斜树：所有的结点都只有左子树的二叉树叫左斜树，只有右子树的叫右斜树，这两者统称为斜树。
斜树
3-2丶满二叉树
在一棵二叉树上，如果所有的分支结点都有左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树叫满二叉树。
满二叉树
3-3丶完全二叉树
对一颗具有n个结点的二叉树按照层次编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树编号为i的结点在此二叉树中的位置完全一样，则称此二叉树为完全二叉树。
完全二叉树
3-4丶二叉树的性质--非常重要
-
性质1:在二叉树的第i层上最多有2^(i-1)个结点(i>=1)。
-
性质2:深度为k的二叉树最多有(2^k)-1个结点(k>=1)。
-
性质3:对于任意一颗二叉树T，如果其终端结点数为N0，度为2的结点数为N2，则N0=N2+1。
二叉树的性质
3-5丶二叉树的顺序存储
二叉树的顺序存储
二叉链表
3-6丶二叉树的遍历
01前序遍历：规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树。
前序遍历
void ProOrderTraverse(Tree T){
if(null == T){
return;
}
printf(“%c”,T-data);
ProOrderTraverse(T->lchild);
ProOrderTraverse(T->rchild);
}
02中序遍历：规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树。
中序遍历
void ProOrderTraverse(Tree T){
if(null == T){
return;
}
ProOrderTraverse(T->lchild);
printf(“%c”,T-data);
ProOrderTraverse(T->rchild);
}
03后序遍历：规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。
后序遍历
void ProOrderTraverse(Tree T){
if(null == T){
return;
}
ProOrderTraverse(T->lchild);
ProOrderTraverse(T->rchild);
printf(“%c”,T-data);
}
04层序遍历：规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层，按从左到右的顺序对结点逐个访问。
层序遍历
3-7丶二叉树的建立
void CreateBiTree(BiTree *T){
TElemType ch;
scanf("%c",&ch);
if('#' == ch){
*T = NULL;
}else{
*T = (BiTree)malloc(sizeof(BiTNode));
if(!*T){
exit(OVERFLOW);
}
(*t)->data = ch;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
}
