数据结构31-树、二叉树定义及术语.ppt

数 据 结 构  第二十二课 树、二叉树定义及术语 第二十二课 树、二叉树定义及术语 本课主题： 树、二叉树定义及术语 教学目的： 掌握树、二叉树的基本概念和术语，二叉树 的性质 教学重点： 二叉树的定义、二叉树的性质 教学难点： 二叉树的性质 授课内容： 一、树的定义和基本术语 1 、树的定义(1) 树是n(n≥0)个结点的有限集。在任意一棵非空树中： (1)有且仅有一个特定的称为根的结点； (2)当n1时,其余结点可分为m(m0)个互不相交的有限集T1,T2,...Tm,其中每一个集合本身又是一棵树,并且称为根的子树. 树的例子：家族，机构等 1 、树的定义(2) 树是包含n个结点的有限集合(n≥0) Tree=(D,R) 其中，D是具有相同性质的数据元素的集合，R是如下描述的二元关 系： 在D中存在唯一一个称为根的元素r0,它在关系R下无前驱； 除结点r0外,K中每个结点对于关系R来说，都有且只有一个前驱。 结点r0外的任何结点r∈R，都存在一个结点序列r0,r1,…,rs, ri-1,ri ∈ R(1=i=s),这样一个结点序列称为根到结点r的路径。 2﹑树的抽象数据类型的定义 ADT Tree 数据对象 D： 数据关系 R： 基本操作 P： InitTree(T); DestroyTree(T); CreateTree(T,definition); ClearTree(T); …… 3﹑树的表示方法 树形表示法： 自然界倒长的树（Knuth开初用正长的树表示） 文氏表示法： 用集合表示 凹入表示法： 类似书目 嵌套括号表示法： 广义表表示法 表示的多样性说明了树的应用的广泛性。 4、树的基本概念(1) 树的结点包含一个数据元素及若干指向其子树的分支。 结点拥有的子树数称为结点的度。 度为0的结点称为叶子或终端结点。 度不为0的结点称为非终端结点或分支结点。 4、树的基本概念(2) 4、树的基本概念(3) 树的度是树内各结点的度的最大值。 结点的子树的根称为该结点的孩子，相应地，该结点称为孩子的双亲。 同一个双亲的孩子之间互称兄弟。 结点的祖先是从根到该结点所经分支上的所有结点。 以某结点为根的子树中的任一结点都称为该结点的子孙。 4、树的基本概念(4) 结点的层次从根开始定义起，根为第一层，根的孩子为第二层。其双亲在同一层的结点互为堂兄弟。 树中结点的最大层次称为树的深度，或高度。 如果将树中结点的各子树看成从左至右是有次序的，则称该树为有序树，否则称为无序树。 森林是m(m=0)棵互不相交的树的集合。 4、树的基本概念(5) 二、二叉树的定义 1﹑二叉树是另一种树型结构 它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。左子树和右子树也是如上定义的二叉树。二叉树不是树的特例。 2﹑二叉树的5种形态 空（二叉树）；只有根结点；根结点和左子树；根结点和右子树；根结点和左右子树。 3﹑一棵深度为k且有2(k)-1个结点的二叉树称为满二叉树，如果有深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称之为完全二叉树。 4﹑抽象数据类型二叉树的定义 (1) ADT BinaryTree{ 数据对象D:D是具有相同特性的数据元素的集合。 数据关系R: 基本操作P: InitBiTree(T); DestroyBiTree(T); CreateBiTree(T,definition); ClearBiTree(T); 4﹑抽象数据类型二叉树的定义 (2) BiTreeEmpty(T); BiTreeDepth(T); Root(T); Value(T,e); Assign(T,e,value); Parent(T,e); LeftChild(T,e); RightChild(T,e); 4﹑抽象数据类型二叉树的定义(3) LeftSibling(T,e); RightSibling(T,e); InsertChild(T,p,LR,c); DeleteChild(T,p,LR); PreOrderTraverse(T,visit()); InOrderTraverse(T,visit()); PostOrderTraverse(T,visit()); LevelOrderTraverse(T,Visit()); }ADT BinaryTree 5、二叉树的性质 四、总结 回目