Hi，欢迎来到中国嵌入式培训高端品牌 - 华清远见嵌入式学院，专注嵌入式工程师培养13年！
全国免费报名电话：400-706-1880
当前位置: >
> 二叉树基本概念讲解及创建
二叉树基本概念讲解及创建
时间：作者：华清远见
世界上的树有千万种，我们这里来学习我们数据结构中的树，它是我们现实生活中倒置的树。之前，我们学习的顺序表，链表，栈、和队列。可以说都是我们的线性结构，也就是我们所谓的一对一的结构，可是现实生活中，我们经常碰到是我们一对多的情况。今天，我们就来研究一下这种一对多的数据结构体-----&树&。那么，什么叫做树呢？
二、树的基本概念简介
&1&树的定义
专业定义：(1)有且只有一个称为根的结点
(2)有若干不相交的子树，这些子树本身也是一颗树。
通俗讲解：
(1)树由结点和边组成
(2)树中除根节点外，每一个节点都有一个父结点，但是 可以用多个子节点。
(3)根结点没有父结点
&2&树中的专业术语
节点 ： 父节点 子节点(老子和儿子) 堂兄弟
度： 结点拥有子树的个数
叶子节点：没有子节点的节点
边 : 一个节点到另一个节点的距离
树的深度：节点的层数， 根节点默认为第一层。
有序 ：树的左右位置不能改变。
&3&树的分类
一般树 ： 任意一个结点的子节点的个数不受限制，则称为一般树。(子节点可以有多个)，如下图：
二叉树(重点)：任意一个节点的子节点的个数最多有两个，且子节点的个数不能更改。
森林：树去掉根结点就称之为森林。
提问：在下图中：
&1&A,B,H,I的度分别是多少?
A:3 B : 2 H: 1 I: 0
&2&叶子节点有哪些?
K ,L,F,G,H,I,J
&3&结点F和I在树中的第几层?
F在第3层。
&4&树的深度是多少?
三、二叉树的特性讲解
&1&二叉树的性质讲解
如下图是一颗二叉树，它有一些特性：
思考：第一层最多有多少个? 1个
第二层最多有多少个? 2 个
第三层最多有多少个? 4 ?
规律：第i层结点最后有2的n - 1次方个。
性质1:二叉树的第i层上的结点最多有2的i - 1次方个节点。
思考：深度为1的二叉树(遍历第一层)一共有多少个节点? 1个
深度为2的二叉树(遍历到第二层)一共有多少个节点? 3个
深度为3的二叉树(遍历到第三层)一共有多少个节点? 7个
规律：深度为k的而出书，最多有2的k次方 - 1个节点。
性质2：深度为k的二叉树最多有2的k次方-1个结点。
性质3：在任意一棵二叉树中，树叶的数目比度数为2的结点的数目多1.
(推导过程入下图所示：)
&2&二叉树的分类
满二叉树：在一颗二叉树中，如果所有的分支节点都存在左子树和右子树，并且所有的叶子节点都在同一层上，这样的二叉树，我们称之为满二叉树。
满二叉树的特点：&1&叶子节点只会出现在最下面一层。
&2&非叶子节点的节点，拥有子树的个数一定为2.
&3&在同样深度的二叉树中，满二叉树的节点个数最多。
完全二叉树：对一颗具有n个结点的二叉树按层进行编号，如果编号为i
(1 &= i &= n)的结点与同样深度的满二叉树节点编号为i的结点
在二叉树中的位置完全相同，则这颗树，我们称之为完全二叉树。
如下图所示。
提问：下面这些树，是完全二叉树吗? 不是
总结：满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
四、二叉树的存储
(1)顺序存储[完全二叉树]
(顺序存储的话，若不是完全二叉树存储没有意义。)
假设下面有一颗树，我们如何把它存到数组中呢?
思路：先把转换成完全二叉树，然后再编号。
这样存储就看似没有什么问题。我们可以按照编号把数据存储到数组中，我们按照编号(1,2,3,4,5)的顺序存储就可以了啊!这个时候，我就要问了，假说说，我们的m的编号，你怎么知道我们的3好位置是在下面，而不是在我们的m编号的位置呢?我们的连续存储无法识别。(这种方法，我们无法推断树的结构)。
因此，我们顺序存储规定：
无论是何种树，我们都会转换成完全二叉树。然后一层一层的从左给我们的二叉树进行编号，然后存储在数组中。及如下图。
那么我们以上的存储有什么规律呢?假设某个节点为i的话，我们来观察一下。
是不是所有的左孩子都是偶数，所有的右孩子都是奇数啊！
完全二叉树的特点：
对于编号为i(i&=1)的结点：
(1)左孩子存在：2 * i &= n(节点的个数)，左孩子编号
(2)右孩子存储：2 * i + 1 &= n,右孩子编号 2 * i + 1
(2)链式存储[完全二叉树]
链式存储：定义结点保存左孩子和右孩子的地址。
思考：上述过程，我们的二叉树应该定义什么样的数据类型来保存结点呢？
&4&二叉树的遍历
(1)层次遍历:从上到下一层一层的遍历
(2)前序遍历:根 、左(左子树)、右(右子树)
(3)中序遍历:左(左子树) 、根 、右(右子树)
(4)后序遍历:左(左子树)、右(右子树)、根
规则：遇到根结点则输出，否则遍历。
层次遍历：ABCDEFGHI
先序遍历：ABDGHCEIF
中序遍历：GDHBAEICF
后序遍历：GHDBIEFCA
完全二叉树的递归创建思路：
1.首先，写一个创建单个节点的函数malloc_bnode，左孩子和右孩子都为空并且填充，我们需要的数据
2.然后写一个创建二叉树的函数create_binarytree()函数。调用malloc_bond
函数创建节点，然后判断结点有没有左孩子和右孩子。
2 *num &= n ，左孩子存在 (num为我们的结点编号，n为我们的结点个数)
再次，调用create_binarytree()创建该编号的孩子。
2 *num + 1 &=n,右孩子存储。
再次，调用create_binarytree()创建该编号的孩子，最后返回根节点。
评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
学院最新动态利用二叉树实现最优证据选择方法--《安阳工学院学报》2014年02期
利用二叉树实现最优证据选择方法
【摘要】：给出了一种从冲突证据中选择一组最优证据的方法,该方法解决了冲突证据合成结果可能出错的问题。给出了证据量与证据离散度的概念,并证明了相关定理。首先利用证据离散度选择出确定程度较大的证据,然后构造出二叉树,并给出了利用二叉树实现最优证据选择的具体步骤。该方法可以减少计算量,可以解决证据冲突问题。
【作者单位】：
【关键词】：
【基金】：
【分类号】：TP18【正文快照】：
0引言证据理论又称D-S证据理论,是一种不确定推理方法[1,2]。证据理论在应用中出现的一个主要问题是,当冲突系数较大时,对各证据进行合成的结果很有可能出错。针对该问题很多学者进行了研究,并提出了很多不同的解决办法。目前主要从两个方面解决该问题,一种观点是认为证据理论
欢迎：、、)
支持CAJ、PDF文件格式，仅支持PDF格式
【参考文献】
中国期刊全文数据库
刘海燕;赵宗贵;刘熹;;[J];电子科技大学学报;2008年05期
孙全,叶秀清,顾伟康;[J];电子学报;2000年08期
邓勇,施文康,朱振福;[J];红外与毫米波学报;2004年01期
李弼程,王波,魏俊,钱曾波,黄玉琪;[J];数据采集与处理;2002年01期
李文立;郭凯红;;[J];系统工程理论与实践;2010年08期
【共引文献】
中国期刊全文数据库
彭颖;沈怀荣;马永一;;[J];Journal of China O2011年03期
贾凡;;[J];北京交通大学学报;2011年02期
邓三鹏;杨雪翠;苗德华;郭世杰;王创荣;;[J];车辆与动力技术;2010年02期
李建国;王晓峰;孙晓明;;[J];兵工自动化;2008年02期
李惊回;黎放;董鹏;谢俊杰;;[J];兵工自动化;2008年10期
项浩;姜礼平;苏思;;[J];兵工自动化;2010年11期
彭颖;沈怀荣;马永一;;[J];兵工学报;2011年01期
唐小娟,吴根秀;[J];江西师范大学学报(自然科学版);2004年04期
王越;韩菁;;[J];重庆理工大学学报(自然科学版);2011年01期
彭渔露;张贤敏;;[J];重庆理工大学学报(自然科学);2012年01期
中国重要会议论文全文数据库
马小平;汪永东;樊阳;;[A];第二十六届中国控制会议论文集[C];2007年
孔鹏程;周健;;[A];2011中国仪器仪表与测控技术大会论文集[C];2011年
瞿红春;丁协宾;;[A];机械动力学理论及其应用[C];2011年
夏俊士;杜培军;张伟;;[A];中国测绘学会2010年学术年会论文集[C];2010年
王前东;陈怀新;;[A];中国雷达行业协会航空电子分会暨四川省电子学会航空航天专委会学术交流会论文集[C];2005年
;[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年
;[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年
;[A];Proceedings of 2010 Chinese Control and Decision Conference[C];2010年
朱林;段献忠;范荣奇;苏盛;;[A];2008中国电力系统保护与控制学术研讨会论文集[C];2008年
马永一;沈怀荣;彭颖;;[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年
中国博士学位论文全文数据库
李建平;[D];哈尔滨工程大学;2010年
刘效武;[D];哈尔滨工程大学;2009年
冯光升;[D];哈尔滨工程大学;2009年
姜延吉;[D];哈尔滨工程大学;2010年
杨锦园;[D];华中科技大学;2010年
杨靖;[D];江南大学;2010年
肖献强;[D];合肥工业大学;2011年
梁伟光;[D];中国科学技术大学;2011年
马健丽;[D];北京邮电大学;2010年
王育红;[D];南京航空航天大学;2010年
中国硕士学位论文全文数据库
杨慧;[D];哈尔滨工程大学;2010年
王玉波;[D];大连理工大学;2010年
纪军;[D];江西师范大学;2010年
李丽;[D];北京服装学院;2010年
史辉;[D];解放军信息工程大学;2010年
刘勰;[D];浙江工商大学;2011年
胡敏;[D];电子科技大学;2011年
张丽;[D];吉林大学;2011年
张建良;[D];合肥工业大学;2011年
王玉成;[D];杭州电子科技大学;2011年
【二级参考文献】
中国期刊全文数据库
何兵;[J];北京航空航天大学学报;2003年10期
梁旭荣;姚佩阳;梁德磊;;[J];电光与控制;2008年12期
刘海燕;赵宗贵;刘熹;;[J];电子科技大学学报;2008年05期
孙全,叶秀清,顾伟康;[J];电子学报;2000年08期
何兵,毛士艺,张有为,李少洪;[J];电子与信息学报;2002年07期
张山鹰,潘泉,张洪才;[J];航空学报;2001年04期
李秋华,李吉成,沈振康,朱振福;[J];红外与毫米波学报;2002年03期
汪洋,郑亲波,张钧屏;[J];红外与毫米波学报;2002年03期
杨善林,朱卫东,任明仑;[J];管理科学学报;2003年05期
蒲书缙;杨雷;杨莘元;胡炜薇;;[J];计算机工程;2006年23期
【相似文献】
中国期刊全文数据库
韩德强;邓勇;韩崇昭;杨艺;蒋雯;侯志强;;[J];控制理论与应用;2011年06期
张航;王一军;罗大庸;;[J];小型微型计算机系统;2010年06期
王波;吴华丽;;[J];电子测量技术;2008年07期
王加阳;周勇;;[J];计算机应用研究;2008年07期
郭华伟;施文康;刘清坤;邓勇;;[J];上海交通大学学报;2006年11期
白剑林;王煜;;[J];系统工程与电子技术;2009年09期
高社生;倪龙强;杨凯;;[J];西北工业大学学报;2009年01期
王一军;罗大庸;张航;;[J];计算机工程与应用;2009年15期
李军伟;程咏梅;潘泉;李耀军;;[J];系统工程与电子技术;2010年11期
曹可劲;赵宗贵;江汉;;[J];模式识别与人工智能;2006年03期
中国重要会议论文全文数据库
胡学钢;刘晓光;;[A];全国第21届计算机技术与应用学术会议（CACIS·2010）暨全国第2届安全关键技术与应用学术会议论文集[C];2010年
杨俊;廖闻剑;彭艳兵;;[A];第十届中国科协年会信息化与社会发展学术讨论会分会场论文集[C];2008年
孔鹏程;周健;;[A];2011中国仪器仪表与测控技术大会论文集[C];2011年
马永一;沈怀荣;彭颖;;[A];'2010系统仿真技术及其应用学术会议论文集[C];2010年
王波;吴华丽;王灿林;;[A];2008中国仪器仪表与测控技术进展大会论文集（Ⅰ）[C];2008年
王雪章;;[A];中国航海科技优秀论文集（2010）[C];2010年
朱靖;王晨熙;鄢茂林;郑义成;;[A];全国第一届信号处理学术会议暨中国高科技产业化研究会信号处理分会筹备工作委员会第三次工作会议专刊[C];2007年
孙怀江;杨静宇;;[A];西部大开发 科教先行与可持续发展——中国科协2000年学术年会文集[C];2000年
肖云;彭进业;王选宏;赵健;;[A];第二十九届中国控制会议论文集[C];2010年
付华;康海潮;梁明广;;[A];煤矿自动化与信息化——第21届全国煤矿自动化与信息化学术会议暨第3届中国煤矿信息化与自动化高层论坛论文集（上册）[C];2011年
中国重要报纸全文数据库
袁正兵?吴丹红;[N];检察日报;2007年
焦红艳;[N];法制日报;2007年
储晓惠;[N];江苏经济报;2007年
郭士辉;[N];人民法院报;2007年
桂庆凯;[N];中国知识产权报;2008年
张蕾蕾;[N];检察日报;2006年
戴玉忠;[N];检察日报;2008年
徐道海;[N];江苏法制报;2005年
山东省胶州市检察院
黄英;[N];检察日报;2008年
张伯晋;[N];检察日报;2011年
中国博士学位论文全文数据库
杨建平;[D];电子科技大学;2012年
田雪怡;[D];哈尔滨工程大学;2012年
王万请;[D];解放军信息工程大学;2013年
梁伟光;[D];中国科学技术大学;2011年
李海生;[D];华南理工大学;2013年
肖建于;[D];中国矿业大学;2012年
孙锐;[D];电子科技大学;2012年
肖文;[D];江西财经大学;2011年
朱卫东;[D];合肥工业大学;2003年
廖明燕;[D];中国石油大学;2010年
中国硕士学位论文全文数据库
王刚;[D];西北工业大学;2002年
方琴芬;[D];合肥工业大学;2006年
张春杰;[D];燕山大学;2011年
杨国宁;[D];太原理工大学;2013年
张军;[D];南昌大学;2007年
周保奎;[D];吉林大学;2013年
黄印林;[D];重庆大学;2005年
高珍伟;[D];合肥工业大学;2008年
武金艳;[D];湖南大学;2010年
贺彦;[D];湖北工业大学;2013年
&快捷付款方式
&订购知网充值卡
400-819-9993
《中国学术期刊（光盘版）》电子杂志社有限公司
同方知网数字出版技术股份有限公司
地址：北京清华大学 84-48信箱 大众知识服务
出版物经营许可证 新出发京批字第直0595号
订购热线：400-819-82499
服务热线：010--
在线咨询：
传真：010-
京公网安备75号拓展阅读5――二叉树扩展案例_百度文库
两大类热门资源免费畅读
续费一年阅读会员，立省24元！
拓展阅读5――二叉树扩展案例
上传于|0|0|暂无简介
阅读已结束，如果下载本文需要使用5下载券
想免费下载本文？
定制HR最喜欢的简历
你可能喜欢}