电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

DS06-树树和二叉树VIP免费

DS06-树树和二叉树_第1页
1/67
DS06-树树和二叉树_第2页
2/67
DS06-树树和二叉树_第3页
3/67
第六章树和二叉树第六章树和二叉树树的概念与定义树的概念与定义二叉树二叉树二叉树的遍历与线索化二叉树的遍历与线索化树和森林树和森林哈夫曼树及其应用哈夫曼树及其应用树的计数树的计数6.16.1树的概念与定义树的概念与定义树的定义:树的定义:树树(tree)(tree)是是n(n≥0)n(n≥0)个结点的个结点的有限集有限集TT,当,当n=0n=0时,称为空树;当时,称为空树;当n>0n>0时,满足以下条件:时,满足以下条件:((11)有且仅有一个结点被称为树根()有且仅有一个结点被称为树根(rooroott)结点;)结点;((22)当)当n>1n>1时,除根结点以外的其余时,除根结点以外的其余n-1n-1个结点可以划分成个结点可以划分成m(m>0)m(m>0)个互不相交的有个互不相交的有限集限集T1,T2,…T1,T2,…,,TmTm,其中每一个集合本,其中每一个集合本身又是一棵树,称为根的子树身又是一棵树,称为根的子树(subtree)(subtree)。。图6.1结点结点(node)(node)::表示树中的元素,包括表示树中的元素,包括数据项及若干指向其子树的分支。数据项及若干指向其子树的分支。结点的度结点的度(degree)(degree)::结点拥有的子树结点拥有的子树的数目。图的数目。图6.16.1中结点中结点AA的度为的度为33。。叶子叶子(leaf)(leaf)::度为度为00的结点称为叶子的结点称为叶子结点,也称为终端结点。图结点,也称为终端结点。图6.16.1中,叶中,叶子结点有:子结点有:KK,,LL,,FF,,GG,,MM,,II,,JJ。。分支结点分支结点::度不为度不为00的结点称为分支结的结点称为分支结点,也称为非终端结点。图点,也称为非终端结点。图6.16.1中,非中,非终端结点有:终端结点有:AA,,BB,,CC,,DD等。等。孩子结点孩子结点(child)(child)::结点的子树的根称结点的子树的根称为该结点的孩子结点。图为该结点的孩子结点。图6.16.1中,结点中,结点AA的孩子结点为的孩子结点为BB,,CC,,DD,结点,结点BB的的孩子结点为孩子结点为EE,,FF。。双亲结点双亲结点(parents)(parents)::孩子结点的上层孩子结点的上层结点称为该结点的双亲结点。图结点称为该结点的双亲结点。图6.16.1中,中,结点结点II的双亲为的双亲为DD,结点,结点LL的双亲为的双亲为EE。。兄弟结点兄弟结点(sibling)(sibling)::具有同一双亲结具有同一双亲结点的孩子结点之间互称为兄弟结点。图点的孩子结点之间互称为兄弟结点。图6.16.1中,结点中,结点BB,,CC,,DD互为兄弟,结互为兄弟,结点点KK,,LL互为兄弟。互为兄弟。树的度树的度::树中最大的结点的度数即为树树中最大的结点的度数即为树的度。的度。图图6.16.1中的树的度为中的树的度为33。。结点的层次结点的层次(level)(level)::从根结点算起,从根结点算起,根为第一层,它的孩子为第二层……。根为第一层,它的孩子为第二层……。若某结点在第若某结点在第ll层,则其孩子结点就在层,则其孩子结点就在第第l+1l+1层。图层。图6.16.1中,结点中,结点AA的层次为的层次为11,结点,结点MM的层次为的层次为44。。树的高度树的高度(depth)(depth)::树中结点的最大层树中结点的最大层次数。图次数。图6.16.1中的树的高度为中的树的高度为44。。森林森林(forest)(forest)::m(m≥0)m(m≥0)棵互不相交棵互不相交的树的集合。的树的集合。有序树与无序树:有序树与无序树:树中结点的各子树从树中结点的各子树从左至右是有次序的(不能互换)则称该树左至右是有次序的(不能互换)则称该树为为有序树有序树,否则称该树为,否则称该树为无序树。无序树。6.26.2二叉树二叉树二叉树的定义:二叉树的定义:二叉树是由二叉树是由n(n≥0)n(n≥0)个个结点的有限集结点的有限集TT构成,此集合或者为空构成,此集合或者为空集,或者由一个根结点及两棵互不相交集,或者由一个根结点及两棵互不相交的左右子树组成,并且左右子树都是二的左右子树组成,并且左右子树都是二叉树。叉树。注意:注意:二叉树的子树有左右之分,因此二叉树的子树有左右之分,因此二叉树是一种有序树。二叉树是一种有序树。二叉树的性质:二叉树的性质:...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

DS06-树树和二叉树

您可能关注的文档

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部