首页 > 知识点讲解
       树的递归定义理解
知识路径: > 计算机科学基础 > 常用数据结构 > 树 > 树和二叉树 > 
相关知识点:10个      
        树是零个或多个节点的有限集合。在一棵非空树中:
        .有一个特定的称为该树之根的节点。
        .除根外的其他节点被分成nn≥0)个不相交的集合T1,T2, …,Tn,其中每个集合本身是一棵树,树T1,T2, …,Tn称为根的子树。
        这是一个递归定义,即在树的定义中又用到树的概念,它指出了树的固有特性,具有一个节点的树必然由根组成,而具有n>1个节点的树则借助于小于n个节点的树来定义。特别要注意的是递归定义中各子树T1,T2, …,Tn的相对次序是重要的,即是有序的。
               树的性质和基本概念
               树包括以下一些基本性质。
               .树中的节点数等于所有节点的度数加1。
               .度为m的树中第i层上至多有mi-1个节点(i≥1)。
               .高度为hm叉树至多有(mh-1)/(m-1)个节点。
               .具有n个节点的m叉树的最小高度为|logmnm-1)+1)|。
               树还包含树的度、节点数及叶子节点数等。关于如何对给定的树求出满足某种条件的树的节点数和叶子节点数等问题,下面列举两个例子来加以说明。
               例1:已知一棵度为m的树中有N1个度为1的节点,N2个度为2的节点,……,Nm个度为m的节点。试问该树中有多少个叶子节点?
               解决该问题的关键是将树的节点数和树中各节点的度联系起来。若设该树中叶子节点个数为N0,则该树节点个数为,因该树节点个数又为,故
               ,即
               例2:已知某度为k的树中,其度为0, 1, 2, …,k-1的节点数分别为n0,n1,n2, …,nk-1,求该树的节点总数。
               设树的度为k的节点数为nk,则树的总节点数为:
               n=n0+n1+…+nk-1+nk
               而树的分支数(或连线数),即n-1为:n-1=n1+2n2+(k-1)nk-1+knk,故
               
 
 相关知识点:
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计(包括造型,颜色,图案,观感,文字,产品,内容),功能及其展示形式,均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部,违者将依法追究责任,特此声明。
本站部分内容来自互联网或由会员上传,版权归原作者所有。如有问题,请及时联系我们。


工作时间:9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有