最新数据结构-06树课件ppt.ppt

《最新数据结构-06树课件ppt.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构-06树第六章二叉树和树树型结构是一类非常重要的非线性数据结构。树是以分支关系定义的层次结构。学院教务科院办基础部科学系技术系计算中心软件系研究所后勤处应用室人工智能室可计算性室学生科师资科教学科教材科第六章二叉树和树6.1二叉树6.1.0树的定义和基本术语6.1.1二叉树的定义和基本术语6.1.2二叉树的几个基本性质6.1.3二叉树的存储结构6.2二叉树遍历6.2.1问题的提出6.2.2遍历算法描述6.2.3二叉树遍历应用举例6.2.4线索二叉树6.3树和森林6.3.1树和森林的定义6.3.2树和森林的存储结构6.3.3树、森林与二叉树

2、的转换6.3.4树和森林的遍历6.4树的应用6.4.1堆排序的实现6.4.2二叉排序树6.4.3赫夫曼树及其应用父结点（parent）和子结点（child）若结点x有一个以结点y为树根的子树,则x为y的父结点（父亲），而y为x的子结点（孩子）。兄弟（sibling）同一个父结点之子结点，称为兄弟如图B、C、D的父结点均为A，故B、C、D互为兄弟结点的度（degree）结点的子树个数，称为结点的度。如图，A的度为3，B的度为3，C的度为1，最大的度值为3，故树为3元树。层次（level）层次为结点之特性值，将根结点之层次设为1，其子结点为2，依此类

3、推。如图，层次为1的有结点A,为2的有结点B、C、D，为3的有结点E、F、G、H、I。6.1.0树的基本术语深度（depth）或高度（height）叶子结点的最大层次数称为树。祖先（ancestor）由某结点X到根结点之路径上的所有结点，均称为X之祖先树林（forest）n(n>=0)个树的集合称为树林若将一树的根结点移去，所剩这恰是一树林.ADCBEFGHIDCBEFGHI6.1.0树的基本术语A6.1.1二叉树的定义和基本术语二叉树（binarytree）是n(n≧0)个数据元素的有限集，它或为空集(n≧0)，或者含有唯一的称为根的元素，且其

4、余元素分成两个互不相交的子集，每个子集自身也是一棵二叉树，分别称为根的左子树和右子树。集合为空的树简称为空树。树中的元素称为结点。ADCBEFBDE左子树CF右子树6.1.1二叉树的定义和基本术语二叉树的子树有左右之分，不能任意颠倒。如图所示A为根结点D、G、H、J为叶子结点A是B的父亲，B是A的左孩子，C是A的右孩子，A是E的祖先，E是A的子孙，D和E是兄弟，D和F是堂兄弟A、B、的度为2，C、F、I的度为1，D、G、H、J的度为0二叉树的深度为5ADCBEGFIJH满二叉树（fullbinarytree）若二叉树中所有的分支结点的度数都为2，

5、且叶子结点都在同一层次上，则称这类二叉树为满二叉树。若该树的高度为h，则此满二叉树的结点为2h-1A层次：1CB层次：2DEFG层次：36.1.1二叉树的定义和基本术语完全二叉树（completebinarytree）假如任意一棵包含n个结点的二叉树中每个结点都可以和同深度的满二叉树中编号为1至n的结点一一对应，则称这类二叉树为完全二叉树。一棵深度为h的完全二叉树中,前h-1层的结点都是满的,且第h层的结点都集中在左侧。满二叉树level最大层的结点均向左靠齐完全二叉树ADCBEF6.1.1二叉树的定义和基本术语6.1.1二叉树的定义和基本术语二

6、叉树的应用——表示家族的血缘关系外曾祖母曾祖父曾祖母曾祖父曾祖母外曾祖母外曾祖父外曾祖父祖父外祖父祖母外祖母父亲母亲男方外曾祖母曾祖父曾祖母曾祖父曾祖母外曾祖母外曾祖父外曾祖父祖父外祖父祖母外祖母父亲母亲女方家庭1家庭2不能有相同结点，否则为近亲结婚！6.1.1二叉树的定义和基本术语二叉树的基本操作定义(1)initBiTree(&T)操作结果：构造一棵空的二叉树T。DestroyBiTree(&T)初始条件：二叉树T存在。操作结果：销毁二叉树TCreateBiTree(&T,definition)初始条件：definition给出二叉树T的定义

7、。操作结果：按definition给出的定义构造二叉树T。BiTreeEmpty(T)初始条件：二叉树T存在。操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE.6.1.1二叉树的定义和基本术语二叉树的基本操作定义(2)BiTreeDepth(T)初始条件：二叉树T存在。操作结果：返回T的深度。Parent(T,e)初始条件：二叉树T存在,e是T中某个结点。操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。LeftChiild(T,e)初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的左孩子。若e无左孩子，则返回“

8、空”。RightChild(T,e)初始条件：二叉树T存在，e是T中某个结点。操作结果：返回e的右孩子。若e无右孩子，则返回“空”。6.