二叉树的顺序存储结构

《二叉树的顺序存储结构》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、5.2二叉树本节主要内容二叉树的定义二叉树的抽象数据类型二叉树的性质二叉树的存储结构5.2.1二叉树的定义二叉树是由n（n≥0）个结点构成的、每个结点最多只有两个子树的有序树。二叉树是这样一种有序树，其中每个结点最多只有一个直接前驱结点，但最多可以有两个直接后继结点。二叉树中所有结点的形态共有５种：空结点、无左右子树结点、只有左子树结点、只有右子树结点和左右子树均存在的结点。5.2.1二叉树的定义满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。完全二叉树如果有一棵具有

2、n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构相同，这样的二叉树称为完全二叉树。5.1.1树的定义下图是一个树的例子，其中图(a)是一棵只有根结点的树；图(b)是一棵有12个结点的一般的树。5.2.2二叉树的抽象数据类型1、数据集合即二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。2、操作集合①　双亲结点parent()②　左孩子结点leftChild()③　右孩子结点rightSibling()5.2.2二叉树的抽象数据类型④　插入左结点insertLeftNode(x)⑤　插入右结点insertRi

3、ghtNode(x)⑥　删除左子树deleteLeftTree()⑦　删除右子树deleteLeftTree()⑧　遍历二叉树traverse(vs)5.2.3二叉树的性质性质1若规定根结点的层次为0，则一棵非空二叉树的第i层上最多有2i(i>=0)个结点。性质2若规定空二叉树树的深度为—1(即根结点的深度为0)，则深度为k的二叉树的最大结点数是2k+1—1(k≥-1)个。性质3具有n个结点的完全二叉树的深度k为不超过log2(n+1)-1的最大整数。性质4对于一棵非空的二叉树，如果叶结点个数为n0，度为2的结点数为n2，则有n0=n2

4、+1。5.2.3二叉树的性质性质5对于具有n个结点的完全二叉树，如果按照从上至下和从左至右的顺序对所有结点从0开始顺序编号，则对于序号为i的结点，有：（1）如果i>0，则序号为i的结点的双亲结点的序号为（i-1)/2（表示整除）；如果i=0，则序号为i结点为根结点，无双亲结点。（2）如果，则序号为i结点的左孩子结点的序号为；如果2×i+1，则序号为i结点无左孩子结点。（3）如果2×i+2

5、结构链式存储结构仿真存储结构5.2.4二叉树的存储结构1、二叉树的顺序存储结构完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到。如图(a)在数组中的存储结构如下:5.2.4二叉树的存储结构1、二叉树的顺序存储结构(续)对于一般的非完全二叉树，可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。例:5.2.4二叉树的存储结构1、二叉树的顺序存储结构(续)5.2.4二叉树的存储结构2、二叉树的链式存储结构二叉树的链式存储结构是用指针建立二叉树中结点

6、之间的关系。二叉树最常用的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据元素data、左孩子结点域leftChild和右孩子结点域rightChild。二叉链存储结构中每个结点的图示结构为：5.2.4二叉树的存储结构2、二叉树的链式存储结构(续)例:5.2.4二叉树的存储结构3、二叉树的仿真指针存储结构二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针构造二叉树中结点之间的逻辑关系。二叉树的仿真二叉链存储结构有仿真二叉链存储结构和三叉链存储结构。下图是

7、前页图(a)的仿真二叉链结构5.2.4二叉树的存储结构3、二叉树的仿真指针存储结构(续)小结由于树的操作实现比较复杂，树又可以转换为二叉树，而二叉树的操作实现相对简单，因此实际使用中经常将树问题转换为二叉树问题来处理。二叉树是这样一种有序树，其中每个结点最多只有一个直接前驱结点，但最多可以有两个直接后继结点。本节介绍了二叉树的基本概念和性质，要求读者掌握二叉树的存储结构，为后续章节学习二叉树的遍历和二叉树的应用打下基础。