第11讲 二叉树的存储结构与遍历ppt课件.ppt

《第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;遍历二叉树遍历：是指按照某种顺序访问