资源描述：
《第5章+树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第五章树和二叉树5.1.1树的定义树(tree)是树型结构的简称。它是一种重要的非线性数据结构。树——或者是一棵空树，即不含有任何结点（元素），或者是一棵非空树，即至少含有一个结点。在一棵非空树中，它有且仅有一个称作根(root)的结点，其余所有结点分属于m个(m≥0)互不相交的集合，每个集合又构成一棵树，称它为根结点的子树(subtree)，并且树的根结点是每棵子树根结点的前驱，相反，每棵子树的根结点是所在树的根结点的后继。显然，树是一种递归定义的数据结构。图5-1就是一棵树T，它由根结点A和两棵子树T1和T2
2、所组成，T1和T2分别位于A结点的左下部和右下部，其中树根结点A是两棵子树的根结点B和C的前驱，相反B和C是A的后继；T1又由它的根结点B和三棵子树T11,T12和T13所组成，这三棵子树分别位于B结点的左下部、中下部和右下部，其中B结点是这三棵子树的根结点D、E和F的前驱，相反它们都是B的后继；T11和T13只含有根结点，不含有子树(或者说子树为空树)，不可再分；T12又由它的根结点E和两棵只含有根结点的子树所组成，每棵子树的根结点分别为H和I，E是H和I的前驱，而H和I均是E的后继；T2由它的根结点C和一棵子
3、树所组成，该子树也只含有一个根结点G，不可再分。图5-1树的结构若采用第一章介绍的二元组来描述一棵树，则为：Tree=(K,R)K={ki
4、1≤i≤n,n≥0,ki∈ElemType}其中n为树中结点数，n=0则为空树，n>0则为非空树。对于一棵非空树，关系R应满足下列条件：(1)有且仅有一个结点没有前驱，该结点被称为树的根；(2)除树根结点外，其余每个结点有且仅有一个前驱结点；(3)包括树根结点在内的每个结点，可以有任意多个(含0个)后继。对于图5-1所示的树T，若采用二元组表示，则结点的集合K和K上二元关系R
5、分别为：K={A,B,C,D,E,F,G,H,I}R={,,,,,,,}5.1.2树的表示树的表示方法有多种。图5-1和5-2中的树形表示法是其中的一种，也是最常用的一种，图5-1和5-2中的结点是从上向下展开的，有时也需要树中的结点按从左向右展开。在树形表示法中，结点之间的关系是通过连线表示的，虽然每条连线上都不带有箭头(即方向)，但它并不是无向的，而是有向的，其方向隐含为从上向下或从左向右，即连线的上方或左边结点是下方或右边结点的
6、前驱，下方或右边结点是上方或左边结点的后继。树的另一种表示法是二元组表示法。除这两种之外，通常还使用广义表表示法，即每棵树的根作为由子树构成的表的名字而放在表的前面，图5-1树T的广义表表示为：A(B(D,E(H,I),F),C(G))5.1.3树的基本术语1.结点的度和树的度2.分支结点和叶子结点3.孩子结点、双亲结点和兄弟结点4.结点的层数和树的深度5.有序树和无序树6.森林5.1.4树的性质性质1树中的结点数等于所有结点的度数加1。性质2度为k的树中第i层上至多有ki-1个结点（i≥1）。性质3深度为h的k
7、叉树至多有(kh-1)/(k-1)个结点。性质4具有n个结点的k叉树的最小深度为5.2二叉树5.2.1二叉树的定义二叉树(binarytree)是指树的度为2的有序树。它是一种树结构,在计算机领域有着广泛地应用。二叉树的递归定义为：二叉树或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的分别称做根的左子树和右子树所组成的非空树，左子树和右子树又同样都是一棵二叉树。5.2.2二叉树的性质性质1二叉树上终端结点数等于双分支结点数加1。性质2二叉树上第i层上至多有2i-1个结点(i≥1)。性质3深度为h的二叉树至多
8、有2h-1个结点。在一棵二叉树中，若除最后一层外，其余层都是满的，而最后一层上的结点可以任意分布，则称此树为理想平衡二叉树,简称理想平衡树或理想二叉树。显然，理想平衡树包含满二叉树和完全二叉树。完全二叉树中深度h和结点数n之间的关系，在理想平衡树中同样成立，因为性质5的证明结果实际上是根据理想平衡树的定义推导出来的。图5-6(a)就是一棵理想平衡树，但它不是完全二叉树；图5-6(b)不是一棵理想平衡树，因它的最后两层都未满。5.2.3二叉树的运算概述(1)初始化二叉树，即把它置为一棵空树。voidInitBTre
9、e(BT);(2)根据广义表表示的二叉树建立对应的存储结构。voidCreateBTree(BT,char*a);(3)判断一棵二叉树是否为空，若是则返回1，否则返回0。intBTreeEmpty(BT);(4)按照一定次序遍历一棵二叉树，使得每个结点的值均被访问一次。voidTraverseBTree(BT);(5)从二叉树中查找值为x的结点，若存在该结点则返回存储位置
