线性结构和非线性结构.ppt

《线性结构和非线性结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、线性结构和非线性结构线性结构的特点是逻辑结构简单，易于进行查找、插入和删除等操作，其主要用于对客观世界中具有单一的前驱和后继的数据关系进行描述。非线性结构是指，在该结构中至少存在一个数据元素，有两个或两个以上的直接前驱（或直接后继）元素。树型结构和图型就是其中十分重要的非线性结构，可以用来描述客观世界中广泛存在的层次结构和网状结构的关系。树二叉树二叉树遍历线索二叉树树和森林哈弗曼树第5章树和二叉树5.1树的概念张源张明张亮张丽张林张维张平张华张君张晶张磊树的定义树是由n(n0)个结点组成的有限集合T。如果n=0，称为空树；如果n>0，则T满足以下两个条件

2、：有且只有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其它结点划分为m(m0)个互不相交的有限集合T1,T2,…,Tm，其中每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。树的表示树型表示bacghdefij凹入表表示abdeijfcgh嵌套集合表示嵌套括号（广义表）表示ijdfghabcea(b(d,e(i,j),f),c(g,h))结点(node)结点的度(degree)结点的子树个数分支(branch)结点度不为0的结点叶(leaf)

3、结点度为0的结点子女(child)结点某结点子树的根结点双亲(parent)结点某个结点是其子树之根的双亲12344兄弟(sibling)结点具有同一双亲的所有结点祖先(ancestor)结点若树中结点k到ks存在一条路径，则称k是ks的祖先子孙(descendant)结点若树中结点k到ks存在一条路径，则称ks是k的子孙结点所处层次(level)根结点的层数为1，其余结点的层数为双亲结点的层数加1树的高度(depth)树中结点的最大层数有序树子树的次序不能互换无序树子树的次序可以互换森林互不相交的树的集合5.2二叉树(BinaryTree)5.2.1二叉

4、树的定义二叉树的五种不同形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i1)5.2.2二叉树的性质证明：i=1时，有2i-1=20=1，成立假定：i=k时性质成立；当i=k+1时，第k+1层的结点至多是第k层结点的两倍，即总的结点个数至多为2×2k-1=2k故命题成立性质2高度为k的二叉树最多有2k-1个结点。(k1)证明：仅当每一层都含有最大结点数时，二叉树的结点数最多，利用性质1可得二叉树的结点数至

5、多为：20+21+22+23+…+2k-1=2k－1等比数列求和Sn＝a1(1-qn)/(1-q)性质3对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0＝n2＋1证明：1、结点总数为度为0的结点加上度为1的结点再加上度为2的结点：n=n0+n1+n22、另一方面，二叉树中一度结点有一个孩子，二度结点有二个孩子，根结点不是任何结点的孩子，因此，结点总数为：n=n1+2n2+13、两式相减，得到：n0=n2+1定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树。定义2完全二叉树(CompleteB

6、inaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(0h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。性质4具有n个结点的完全二叉树的高度为log2n+1证明：设完全二叉树的高度为h，则有2h-1-1

7、若i>1,则i的双亲为i/2若2*i<=n,则i的左子女为2*i；否则，i无左子女，必定是页结点，二叉树中i>n/2的结点必定是页结点若2*i+1<=n,则i的右子女为2*i+1，否则，i无右子女若i为奇数,且i不为1，则其左兄弟为i-1，否则无左兄弟；若i为偶数,且小于n，则其右兄弟为i+1，否则无右兄弟i所在层次为log2(i)+11243568910711121314151617完全二叉树的数组表示一般二叉树的数组表示5.2.3二叉树的存储顺序存储结构#defineMAXSIZE100typedefintElemType;typedefS

8、equenBiTree[MAXSIZE];单支树由于一般二叉树必须