资源描述：
《考研数据结构chapt6.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树数据结构:线性结构(线性表,栈,队列等)非线性结构:至少存在一个数据元素有不止一个直接前驱或后继(树,图等)第六章树和二叉树§6.1树的定义树是n个数据元素的有限集(记为T)，对任意一棵树T有：⒈存在唯一一个称为根的数据元素；⒉当n＞1时，其它数据元素可分为m(m＞0)个互不相交的有限集T1,T2,…,Tm，其中每个集合Ti(i=1,2,…,m)本身又是一棵树，并称树Ti是根的子树.第六章树和二叉树树的表示法1.分支图表示法2.嵌套集合表示法ABCDABCD3.广义表表示法(A(B(D),C))第六章树和二叉树树的基本术语1.树的结点:包含一个DE和指向其子树的所有分支;2.结
2、点的度:一个结点拥有的子树的个数,度为零的结点称为叶结点;3.树的度:树中所有结点的度的最大值Max(D(I))含义:树中最大分支数为树的度;4.结点的层次及树的深度:根为第一层,根的孩子为第二层,若某结点为第k层,则其孩子为k+1层.树中结点的最大层次称为树的深度或高度5.森林:是m(m>=0)棵互不相的树的集合森林与树概念相近,相互很容易转换.第六章树和二叉树§6.2树的基本运算⒈初始化操作INITIATE(T)：创建一棵空树。⒉求根函数ROOT(T)：求树T的根；ROOT(X)：求结点x所在树的根。⒊求双亲函数PARENT(T,x)：在树T中求x的双亲。⒋求第i个孩子函数CHILD(T,
3、x,i)：在树T中求结点x的第i个孩子。⒌求兄弟函数：在T中求x的左兄弟LSIBLING(T,x)；在树T中求x的右兄弟RSIBLING(T,x)。第六章树和二叉树⒍建树函数CRT-TREE(x,F)：建立以结点x为根，森林F为子树的树。⒎插入子树操作INS-CHILD(y,i,x)：将x作为y的第i根子树。⒏删除子树操作DEL-CHILD(x,i)：删除x的第i棵子树。⒐遍历树操作TRAVERSE(T)：按顺序访问树T中各个结点。⒑置空树操作CLEAR(T)：将树T置为空树。第六章树和二叉树§6.3二叉树概念及性质一.二叉树概念二叉树是结点数为0或每个结点最多只有左右两棵子树的树。二叉树是一
4、种特殊的树，它的特点是：⑴每个结点最多只有两棵子树，即不存结点度大于2的结点；⑵子树有左右之分，不能颠倒。6.3二叉树二.二叉树性质性质1.在二叉树的第i层上至多有2i-1个结点(i≥1)。性质2.深度为k的二叉树至多有2k-1个结点(k≥)。（深度一定，二叉树的最大结点数也确定）性质3.二叉树中,终端结点数n0与度为2的结点数n2有如下关系:n0=n2+16.3二叉树满二叉树:深度为k，且有2k-1个结点的二叉树。特点：（1）每一层上结点数都达到最大（2）度为1的结点n1=0结点层序编号方法：从根结点起从上到下逐层（层内从左到右）对二叉树的结点进行连续编号。1237654K=3n=23-1=
5、7满二叉树6.3二叉树完全二叉树:深度为k，结点数为n的二叉树，当且仅当每个结点的编号都与相同深度的满二叉树中从1到n的结点一一对应时，称为完全二叉树。452136.3二叉树完全二叉树的特点:（1）每个结点i的左子树的深度Lhi-其结点i的右子树的深度Rhi等于0或1，即叶结点只可能出现在层次最大或次最大的两层上。（2）完全二叉树结点数n满足2k-1-1＜n≤2k-1（3）满二叉树一定是完全二叉树，反之不成立。452136.3二叉树LH2=0RH2=11324653241LH1=3RH1=1LH1-RH1=2非完全二叉树非完全二叉树LH2-RH2=0-1=-16.3二叉树性质4.结点数为n的完
6、全二叉树，其深度为└log2n┘+16.3二叉树性质5.在按层序编号的n个结点的完全二叉树中，任意一结点i(1≤i≤n)有：⑴i=1时，结点i是树的根；否则(i>1)，结点i的双亲为结点└i/2┘。⑵2i＞n时，结点i无左孩子，为叶结点；否则，结点i的左孩子为结点2i。⑶2i+1＞n时，结点i无右孩子；否则，结点i的右孩子为结点2i+1。6.3二叉树完全二叉树DCGFEBA三、二叉树的存储结构⒈顺序存储结构用一组地址连续的存储单元，以层序顺序存放二叉树的数据元素，结点的相对位置蕴含着结点之间的关系。bt[3]的双亲为└3/2┘=1，即在bt[1]中；其左孩子在bt[2i]=bt[6]中；其右孩
7、子在bt[2i+1]=bt[7]中。1234567891011ABCDEFG00006.3二叉树这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。D二叉树CGFEBA1234567891011ABCDE0000FG0000一般二叉树也按完全二叉树形式存储,没结点处用0表示。6.3二叉树例如，深度为
