树的概念和定义.pptx
《树的概念和定义.pptx》由会员分享,可在线阅读,更多相关《树的概念和定义.pptx(43页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、 树是n(n0)个结点的有限集合T。当n=0时,称为空树;当n0时,该集合满足如下条件:(1)其中必有一个称为根(root)的特定结点,它没有直接前驱,但有零个或多个直接后继。(2)其余n-1个结点可以划分成m(m0)个互不相交的有限集T1,T2,T3,Tm,其中Ti又是一棵树,称为根root的子树。每棵子树的根结点有且仅有一个直接前驱,但有零个或多个直接后继。第1页/共43页图6.1 树的图示方法第2页/共43页结点:包含一个数据元素及若干指向其它结点的分支信息。结点的度:一个结点的子树个数称为此结点的度。叶结点:度为0的结点,即无后继的结点,也称为终端结点。分支结点:度不为0的结点,也称为
2、非终端结点。孩子结点:一个结点的直接后继称为该结点的孩子结点。双亲结点:一个结点的直接前驱称为该结点的双亲结点。兄弟结点:同一双亲结点的孩子结点之间互称兄弟结点。第3页/共43页祖先结点:一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图中,结点K的祖先是A、B、E。子孙结点:一个结点的直接后继和间接后继称为该结点的子孙结点。在图中,结点D的子孙是H、I、J、M。树的度:树中所有结点的度的最大值。结点的层次:从根结点开始定义,根结点的层次为1,根的直接后继的层次为2,依此类推。树的高度(深度):树中所有结点的层次的最大值。有序树:在树T中,如果各子树Ti之间是有先后次序的,则称为有
3、序树。森林:m(m0)棵互不相交的树的集合。将一棵非空树的根结点删去,树就变成一个森林;反之,给森林增加一个统一的根结点,森林就变成一棵树。第4页/共43页 ADT Tree 数据对象D:一个集合,该集合中的所有元素具有相同的特性。数据关系R:若D为空集,则为空树。若D中仅含有一个数据元素,则R为空集,否则R=H,H是如下的二元关系:(1)在D中存在唯一的称为根的数据元素root,它在关系H下没有前驱。(2)除root以外,D中每个结点在关系H下都有且仅有一个前驱。第5页/共43页 基本操作:(1)InitTree(Tree):将Tree初始化为一棵空树。(2)DestoryTree(Tree
4、):销毁树Tree。(3)CreateTree(Tree):创建树Tree。(4)TreeEmpty(Tree):若Tree为空,则返回TRUE,否则返回FALSE。(5)Root(Tree):返回树Tree的根。(6)Parent(Tree,x):树Tree存在,x是Tree中的某个结点。若x为非根结点,则返回它的双亲,否则返回“空”。第6页/共43页(7)FirstChild(Tree,x):树Tree存在,x是Tree中的某个结点。若x为非叶子结点,则返回它的第一个孩子结点,否则返回“空”。(8)NextSibling(Tree,x):树Tree存在,x是Tree中的某个结点。若x不是其
5、双亲的最后一个孩子结点,则返回x后面的下一个兄弟结点,否则返回“空”。第7页/共43页 (9)InsertChild(Tree,p,Child):树Tree存在,p指向Tree中某个结点,非空树Child与Tree不相交。将Child插入Tree中,做p所指向结点的子树。(10)DeleteChild(Tree,p,i):树Tree存在,p指向Tree中某个结点,1id,d为p所指向结点的度。删除Tree中p所指向结点的第i棵子树。(11)TraverseTree(Tree,Visit():树Tree存在,Visit()是对结点进行访问的函数。按照某种次序对树Tree的每个结点调用Visit(
6、)函数访问一次且最多一次。若Visit()失败,则操作失败。第8页/共43页二叉树的定义与基本操作 第9页/共43页 定义:我们把满足以下两个条件的树形结构叫做二叉树(Binary Tree):(1)每个结点的度都不大于2;(2)每个结点的孩子结点次序不能任意颠倒。由此定义可以看出,一个二叉树中的每个结点只能含有0、1或2个孩子,而且每个孩子有左右之分。我们把位于左边的孩子叫做左孩子,位于右边的孩子叫做右孩子。第10页/共43页图给出了二叉树的五种基本形态。第11页/共43页 与树的基本操作类似,二叉树有如下基本操作:(1)Initiate(bt):将bt初始化为空二叉树。(2)Create(
7、bt):创建一棵非空二叉树bt。(3)Destory(bt):销毁二叉树bt。(4)Empty(bt):若bt为空,则返回TRUE,否则返回FALSE。(5)Root(bt):求二叉树bt的根结点。若bt为空二叉树,则函数返回“空”。第12页/共43页(6)Parent(bt,x):求双亲函数。求二叉树bt中结点x的双亲结点。若结点x是二叉树的根结点或二叉树bt中无结点x,则返回“空”。(7)LeftChild(bt,x):求左孩子。若结点x为叶子结点或x不在bt中,则返回“空”。(8)RightChild(bt,x):求右孩子。若结点x为叶子结点或x不在bt中,则返回“空”。(9)Trave
8、rse(bt):遍历操作。按某个次序依次访问二叉树中每个结点一次且仅一次。(10)Clear(bt):清除操作。将二叉树bt置为空树。第13页/共43页二叉树的性质 第14页/共43页 性质1:在二叉树的第i层上至多有2i-1个结点(i1)。证明:用数学归纳法。归纳基础:当i=1时,整个二叉树只有一根结点,此时2i-1=20=1,结论成立。归纳假设:假设i=k时结论成立,即第k层上结点总数最多为2k-1个。现证明当i=k+1时,结论成立:因为二叉树中每个结点的度最大为2,则第k+1层的结点总数最多为第k层上结点最大数的2倍,即22k-1=2(k+1)-1,故结论成立。第15页/共43页 性质2
9、:深度为k的二叉树至多有2k-1个结点(k1)。证明:因为深度为k的二叉树,其结点总数的最大值是将二叉树每层上结点的最大值相加,所以深度为k的二叉树的结点总数至多为 故结论成立。第16页/共43页 性质3:对任意一棵二叉树T,若终端结点数为n0,而其度数为2的结点数为n2,则n0=n2+1。证明:设二叉树中结点总数为n,n1为二叉树中度为1的结点总数。因为二叉树中所有结点的度小于等于2,所以有n=n0+n1+n2 设二叉树中分支数目为B,因为除根结点外,每个结点均对应一个进入它的分支,所以有n=B+1第17页/共43页 又因为二叉树中的分支都是由度为1和度为2的结点发出,所以分支数目为B=n1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 概念 定义
限制150内