西科大-数据结构4.ppt

《西科大-数据结构4.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、计算机软件技术基础数据结构与算法（4）数据结构研究的内容22.4树和二叉树特点：非线性结构，一个直接前驱，但可能有多个直接后继。2.4.1树的基本概念2.4.2二叉树2.4.3遍历二叉树（一对多或1:n）32.4.1树的基本概念由一个或多个(n≥0)结点组成的有限集合T，有且仅有一个结点称为根（root），当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树。4若干术语——即上层的那个结点(直接前驱)——即下层结点的子树的根(直接后继)——同一双亲下的同层结点（孩子之间互称兄弟）——即双亲位于同一层的结点（但并非

2、同一双亲）——即从根到该结点所经分支的所有结点——即该结点下层子树中的任一结点ABCGEIDHFJFLK根叶子森林有序树无序树——即根结点(没有前驱)——即终端结点(没有后继)——指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙——结点各子树从左至右有序，不能互换（左为第一）——结点各子树可互换位置。5——即树的数据元素——结点挂接的子树数结点结点的度结点的层次终端结点分支结点树的度树的深度(或高度)——从根到该结点的层数（根结点算第一层）——即度为0的结点，即叶子——即度不为0的结点（也称为内部结点）——所有结点度中的最大值（Max{各结点的度}）——

3、指所有结点中最大的层数（Max{各结点的层次}）问：右上图中的结点数＝；树的度＝；树的深度＝1334（有几个直接后继就是几度，亦称“次数”）ABCGEIDHFJFLK6树的逻辑结构一对多（1:n），有多个直接后继（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。特点：一般树（即多叉树）的物理结构比较复杂，而且运算也很难实现。解决方法：将多叉树转化为等价的二叉树。树的物理结构7为何要重点研究每结点最多只有两个“叉”的树？二叉树的结构最简单，规律性最强；可以证明，所有树都能转为唯一对应的二叉树，不失一般性。1.二叉树的定义2.二叉树的性质3.二叉树的存储结构2.4.2二

4、叉树81.二叉树的定义定义：是n（n≥0）个结点的有限集合，或者是（n=0），或者是由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。逻辑结构：一对二（1:2）基本特征:①每个结点最多只有两棵子树（不存在度大于2的结点）；②左子树和右子树次序不能颠倒。问：具有3个结点的二叉树可能有几种不同形态？有5种。基本形态：92.二叉树的性质(3+2)讨论1：第i层的结点数最多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第i层上至多有2i-1个结点（i>0）。性质2:深度为k的二叉树至多有2k-1个结点（k>0）。再提问：第i层上至少有个结点？1讨论2：深度为k的

5、二叉树，最多有多少个结点？（利用二进制性质可轻松求出）2i-1个2k-1个10性质3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n2＋1（即n0=n2+1）证明：∵二叉树中全部结点数n＝n0+n1+n2(叶子数＋1度结点数＋2度结点数)又∵二叉树中全部结点数n＝B+1(总分支数＋根结点)（除根结点外，每个结点必有一个直接前趋，即一个分支）而总分支数B=n1+2n2(1度结点必有1个直接后继，2度结点必有2个)三式联立可得：n0+n1+n2=n1+2n2+1,即n0=n2+1物理意义：叶子数＝2度结点数＋1讨论3：二叉树的叶子数和度为2的结点数之间有关系吗？

6、11性质4:具有n个结点的完全二叉树的深度必为log2n＋1性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1时为根,除外）。证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即2k-1-1

7、还特别具备以下2个性质：12完全二叉树：深度为k的、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为它们在顺序存储方式下可以复原！满二叉树：一棵深度为k且有2k-1个结点的二叉树。（特点：每层都“充满”了结点）满二叉树和完全二叉树有什么区别？答：满二叉树是叶子一个也不少的树，而完全二叉树虽然前k-1层是满的，但最底层却允许在右边缺