程序设计技术--第五章-树形结构.ppt

《程序设计技术--第五章-树形结构.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1程序设计技术第五章树形结构2第三部分树形结构树的概念和基本术语二叉树树的二叉树表示二叉树遍历树的遍历霍夫曼树3树的概念和基本术语树的定义树是由n(n0)个结点的有限集合。如果n=0，称为空树；如果n>0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n>1，除根以外的其它结点划分为m(m>0)个互不相交的有限集T1,T2,…,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。4ACGBDEFKLHMIJ例如A只有根结点的树有13个结点的树其中：A是根；其余结点分成三个互不相交的子集，T1={B,

2、E,F,K,L}；T2={C,G}；T3={D,H,I,J,M},T1,T2,T3都是根A的子树，且本身也是一棵树5树的基本术语1层2层4层3层height=4ACGBDEFKLHMIJ6二叉树(BinaryTree)定义五种形态一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LLRR特点每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）7性质1在二叉树的第i层上至多有2i－1个结点。(i1)[证明用归纳法]性质2深度为k的二叉树至多有2k-1个结点(k1)。性质3对任何

3、一棵二叉树T,如果其叶结点数为n0,度为2的结点数为n2,则n0＝n2＋1.性质8定义1满二叉树(FullBinaryTree)一棵深度为k且有2k-1个结点的二叉树称为满二叉树。两种特殊形态的二叉树621754389101113141512满二叉树92154367216543非完全二叉树定义2完全二叉树(CompleteBinaryTree)若设二叉树的高度为h，则共有h层。除第h层外，其它各层(1h-1)的结点数都达到最大个数，第h层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树10完全二叉树一般二叉树的顺序表示

4、的顺序表示二叉树的存储结构112345678910912340567800910248910567312365478顺序表示91011链表表示lChilddatarChilddatalChildrChild二叉链表含两个指针域的结点结构lChilddataparentrChild含三个指针域的结点结构parentdatalChildrChild三叉链表12二叉树链表表示的示例AAABBBCCCDDDFFFEEErootrootroot二叉树二叉链表三叉链表13typedefcharTreeData;//结点数据类型typed

5、efstructnode{//结点定义TreeDatadata;structnode*leftChild,*rightchild;}BinTreeNode;typedefBinTreeNode*BinTree;//根指针二叉链表的定义14结点结构datafirstChildnextSiblingABCDEFG空链域n+1个树的左子女-右兄弟表示（二叉链表表示）BCDGFEA树的二叉树表示15树的二叉树表示:ABCDEFGABCEDGF16T1T2T3T1T2T3AFHBCDGIJEKAFBCDEGHIKJABCEDHIKJFG3棵树的森林

6、各棵树的二叉树表示森林的二叉树表示森林与二叉树的转换17二叉树遍历树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作V遍历根的左子树记作L遍历根的右子树记作R则可能的遍历次序有前序VLR中序LVR后序LRVVLR18中序遍历二叉树算法的定义：若二叉树为空，则空操作；否则中序遍历左子树(L)；访问根结点(V)；中序遍历右子树(R)。遍历结果a+b*c-d-e/f中序遍历(InorderTraversal)--/+*abcdef19前序遍历二叉树算法的定义：若二叉树为空，则空操作；否则访问根结点(V)；前序遍历左子树(L

7、)；前序遍历右子树(R)。遍历结果-+a*b-cd/ef前序遍历(PreorderTraversal)--/+*abcdef20后序遍历二叉树算法的定义：若二叉树为空，则空操作；否则后序遍历左子树(L)；后序遍历右子树(R)；访问根结点(V)。遍历结果abcd-*+ef/-后序遍历(PostorderTraversal)--/+*abcdef21树的遍历深度优先遍历先根次序遍历后根次序遍历22深度优先遍历当树非空时访问根结点依次先根遍历根的各棵子树树先根遍历ABEFCDG对应二叉树前序遍历ABEFCDG树的先根遍历结果与其对应二叉树表示的前序遍历结果相同

8、树的先根遍历可以借助对应二叉树的前序遍历算法实现ABCEDGF树的先根次序遍历A