欢迎来到天天文库
浏览记录
ID:59197768
大小:911.00 KB
页数:37页
时间:2020-09-26
《第11讲 二叉树的存储结构与遍历ppt课件.ppt》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、第11讲二叉树的存储结构与遍历主讲人:陈红丽(1)具有n个结点的非空二叉树的最小深度是多少?最大深度是多少?课前问题(2)具有n个结点的完全二叉树中有多少个叶子结点?有多少个度为2的结点?(3)具有n0个叶子结点的完全二叉树中共有多少个结点?答:最小深度是log2n+1,最大深度是n。答:有n/2个叶子结点,有n/2-1个度为2的结点。答:共有2n0个结点或2n0-1个结点。二叉树的存储结构顺序存储结构依照层序编号规则,存放各个结点。存储位置隐含树的关系。二叉树的顺序存储结构的定义如下://暂定二叉树中结点数的最大值为100constintMAXSIZE=
2、100;typedefstruct{TElemType*data;//存储空间基址(初始化时分配空间)intnodeNum;//二叉树中结点数}SqBiTree;//二叉树的顺序存储结构对于完全二叉树,将完全二叉树上编号为i的结点元素存储在一维数组中下标为i-1的分量中0123456789101112…m-1Bi.dataabckdehilfgjabcdefghijkl练习:将68个结点的完全二叉树,按顺序存储结构存于数组A[0…100]中,最小编号的叶子结点存储于A[]。A、32B、33C、34D、35C对于一般二叉树的顺序存储:将其每个结点与完全二叉树上的结点相对照
3、,然后存储在数组的相应分量中,缺少的结点用“0”补齐。abchdef0123456789101112…m-1Bi.dataabcde0000fh画出二叉树分支图表示写出结点c的父结点及其左、右孩子二叉树采用顺序存储结构,如下图所示1234567891011121314151617181920eafdgckhibafedgckhbi1234567891011121314151617181920eafdgckhib结点c的父结点是结点d;结点c的左孩子是结点b、没有右孩子。采用顺序存储结构,深度为k且只有k个结点的右单枝树(每个非叶结点只有右孩子),需要()个单元,即有()
4、个单元被浪费。2k-12k-1-k二叉树的链式存储结构dataparentlchildrchild(a)二叉树的结点lchilddatarchild(b)含两个指针的结点结构(c)含三个指针的结点结构lchilddatarchildparent根据设计的不同结点结构,构成了不同的链式存储结构。常用的有:二叉链表三叉链表双亲链表线索链表ABCDEFG二叉树逻辑结构ABCDEFG^^^^^^^^二叉链表(存储结构)二叉链表data域存放该结点的数据信息;lchild域与rchild域分别存放指向左、右孩子的指针,当左、右孩子不存在时,相应指针域值为空(用符号∧或NULL表示
5、)。lchilddatarchild结点结构RoottypedefstructBiTNode{ TElemTypedata; structBiTNode*lchild;//左孩子指针structBiTNode*rchild;//右孩子指针}BiTNode;typedefBiTNode*BiTree;lchilddatarchild结点结构ABCDEFG^^^^^^^^二叉链表RootBiTreeRoot;性质6:含有n个结点的二叉链表中,有()个空链域。证明:空链域数=2n0+n1因为n=n0+n1+n2(1)又有n0=n2+1即-1=n2-n0(2)(1)-(2)
6、得出n+1=2n0+n1故空链域数=n+1n+1ABCDEFG^^^^^^^^二叉链表RootABCDEFG二叉树三叉链表结点结构lchilddataparentrchildABCDEFG^^^^^^^^^三叉链表typedefstructTriTNode{TElemTypedata;structTriTNode*lchild;structTriTNode*rchild;structTriTNode*parent;}TriTNode;typedefTriTNode*TriTree;TriTreeRoot;Root结点结构:双亲链表dataparentABDCEF0B41
7、D42C03E14A-15F36LRTagLRRRLRootconstintMAX_TREE_SIZE=100;typedefstructBPTNode{//结点结构TElemTypedata;int*parent;//指向双亲的指针charLRTag;//左、右孩子标志域}BPTNode;typedefstructBPTree{//树结构BPTNodenodes[MAX_TREE_SIZE];intnum_node;//实际结点数目introot;//根结点的位置}BPTree;BPTreeRoot;遍历二叉树遍历:是指按照某种顺序访问
此文档下载收益归作者所有