数据结构中的树、图、查找、排序

《数据结构中的树、图、查找、排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构树、图、查找、排序树:是n(n≥0)个结点的有限集合。如果该集合为空，称为空树。在任意一棵非空树中:ABCDEFKLGHIJM树的定义有且仅有一个特定的称为根结点(root)的结点;2)其他结点可分为若干个互不相交的子集,而且每一个子集本身又是一棵树,称为根的子树。递归定义结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支结点分支的个数,即子树的数目如：A的度-3；B的度-2；K的度-0；树中所有结点的度的最大值如：树的度为3；度为零的结点，也称终端结点如例：K，L，F，G，M，I，J为终端结点度大于零的

2、结点如例：A,B,C,D,E基本术语612345森林：是m（m≥0）棵互不相交的树的集合ArootBEFKLCGDHIJMF~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树型结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)7.2二叉树二叉树或为空树；或是由一个根结点加上两棵分别称为左和右子树的、互不交的二叉树组成。ABCDEFGHK根结点左子树右子树EF特点：1）每个结点最多只有两棵子树；2）两颗子树有

3、左右之分，顺序不能换。二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树特殊的二叉树：满二叉树满二叉树：指的是深度为k且含有2k-1个结点的二叉树。1234567891011121314151234567深度为3，节点数=23-1=7深度为4，节点数=24-1=15特点：1）每一层上的结点数都是最大结点数；2）叶子结点都在最后一层。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。12345612345612345特点：1）除了最下一层外其余各层都是满的；2）最下一层的结

4、点都集中在该层的左侧。12345678910特殊的二叉树：完全二叉树性质1：满二叉树的第i层上有2i-1个结点(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1时，只有一个根结点，2i-1=20=1；假设第j层有2j-1结点，命题成立;第j层的每个结点都有2个结点，则第(j+1)层上的结点数=2*2j-1=2j=2(j+1)-1。二叉树的性质1234567性质1的推论：在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2：深度为k的满二叉树共有2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的满二叉树上的结点数为：

5、20+21++2k-1=2k-1性质2的推论：深度为k的二叉树上最多有2k-1个结点（k≥1）性质3：设二叉树叶子结点数为n0，度为2的结点数为n2，则必存在关系式：n0=n2+1。性质4：具有n个结点的完全二叉树的深度为log2n+1性质5：对于具有n个结点的完全二叉树，如果按照从上到下和从左至右的顺序对二叉树中的所有结点从1至n进行编号，则对于任意的序号为i的结点，有：若i>1，则序号为i的结点的双亲结点的序号为i/2；如果i=1，则该结点是根，无双亲;若2i<=n，则该结点的左孩子结点的序号为2i；否则，如2i>

6、n则该结点无左孩子；若2i+1<=n，则i结点的右孩子结点的序号为2i+1；如果2i+1>n，则序号为i的结点无右孩子结点。二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示用一组连续的存储单元存储二叉树的数据元素,以结点存储的相对位置表示结点之间的关系。为了正确地反映结点之间的关系,任何二叉树都必须按照完全二叉树的形式来存储.这种存储方式对某些二叉树的存储会造成存储空间的浪费。顺序存储结构在高级语言中,可以用一维数组来描述这种顺序存储结构。例如：ABCDFABCDE完全二叉树的顺序存储存储位置123456数据元素ABC

7、DEF一般二叉树的存储存储位置123456数据元素ABCффDNOTES:ф代表空元素#defineMAX_TREE_SIZE100//二叉树的最大结点数TElemTypeSqBiTree[MAX_TREE_SIZE];//1号单元存储根结点例如:ABDCEF1234567891011121314ABCDEF练习：1．已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为（　　　）A．7B．8C．9D．102．若一棵二叉树有11个叶子结点，则该二叉树中度为2的结点个数是（　　　）A．10B．11C．12D．不确定的已知一棵二叉

8、树的顺序存储序列为：aebфfcd，则：1）e的左孩子是哪个结点？右孩子是哪个结点？2）d的双亲是哪个结点？答案：B答案：A答案：1）没有左孩子；右孩子是f；2）b；练习：3．假设一棵二叉树的顺序存储结构如图所示，请回答