数据结构—第六章

《数据结构—第六章》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、数据结构第六章树和二叉树引言线性表中的数据是1：1的关系。树中的数据是1：n的关系。树在生活中应用比较广泛，如：家谱、组织机构等。6.1树的定义和基本术语树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n>0，则：有且仅有一个特定的称之为根结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树。ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集，T1={B,E,F,K,L}；T

2、2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树6.1树的定义和基本术语结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树个数。终端结点（叶子结点）：度为0的结点。非终端结点（分支结点）：度不为0的结点。6.1树的定义和基本术语树的度：树中结点的度的最大值。孩子：结点的子树的根。双亲：该结点。兄弟：同一个双亲的孩子。祖先：从根到该结点所经分支上的所有结点。子孙：该结点的所有子树中的结点。6.1树的定义和基本术语结点的层次：从根开始定义，根在第一层，依次向下。堂兄弟：在同一层次的结点。

3、深度：树中结点的最大层次。6.1树的定义和基本术语有序树：树中结点的各子树从左到右是有次序的。无序树。森林：ｍ颗互不相交的树的集合。6.1树的定义和基本术语树的表示：嵌套表示广义表表示凹入表示树的抽象数据描述P1186.2二叉树二叉树：是由n(n>=0)个结点的有限集合构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。特点：不存在度大于2的结点；二叉树的子树有左右之分，不允许颠倒。6.2二叉树五种形态：LLRR6.2.2二叉树的性质性质1在二叉树的第i层上至多有2i－1个结点。(i1)证明：数学归纳法（

4、1）当i=1时，只有根结点，2i-1=20=1。（2）设当i=k时，第k层上的2k-1个结点成立。则当i=k+1时，第k层上的2k-1个结点每个都可以产生1个或2个结点。所以，第k+1层上至多有：2*2k-1=2k6.2.2二叉树的性质性质2深度为k的二叉树至多有2k-1个结点(k1)。证明：深度为k的二叉树的最大的结点时为二叉树中每层上的最大结点数之和，由性质1得到每层上的最大结点数，所以有：性质3对任何一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为N,二叉树

5、中的分支总数为B。(1)N＝n0＋n1＋n2(2)N＝B＋1=2n2+n1+0*n0+1=2n2+n1+1所以：n0＝n2＋1满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。我们按照由上到下，由左到右的顺序对结点进行顺序编号。两种特殊形态的二叉树621754389101113141512满二叉树2154367216543完全二叉树：如果深度为k、由n个结点的二叉树中，每个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树，称作完全二叉树。6217543891011126.2.2二叉树的性质完全二叉树的特点是：除最深

6、层次外每层都有（）个结点。若有右子树，则一定有左子树。所有的叶结点都出现在第（）层。对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为（）。性质4具有n(n0)个结点的完全二叉树的深度为log2(n)＋1证明：设完全二叉树的深度为k，则根据性质2和完全二叉树的定义有2k－1-1

7、i>1,则i的双亲为i/2。若2*i>n,则i无左孩子；否则其左孩子是2*i。若2*i+1>n,则i无右孩子；否则其右孩子是2*i+1。6217543891011126.2.2二叉树的性质练习：已知一棵完全二叉树，共有700个结点。求叶子结点的个数。6.2.3二叉树的存储结构顺序存储结构：用一组连续的存储单元存储二叉树的数据元素。为了体现层次、父子关系，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系。所以我们约定对于完全二叉树按照结点编号存储，而对于普通二叉树则将其结点与完全二叉树相对照进行存

8、储。完全二叉树一般二叉树的顺序表示的顺序表示二叉树的存储结构1123456789109123405678009102489