频道栏目
首页 > 程序开发 > 综合编程 > 其他综合 > 正文
数据结构之二叉树
2017-02-15 10:46:22         来源:xiangzhihong8的专栏  
收藏   我要投稿

数据结构之二叉树:满足以下条件的就是树:1. 有且仅有一个特定的称为根Root的结点。2. 当n>1时,其余结点可分为m(m>0)个互不相交的有限集,其中每个集合本身又是一个棵树,并称为根的子树。

树是数据结构中一种常见的数据结构,比如我们排序中常见的二叉树,红黑树等。最常见的是树形表示法和广义表表示法。树的结构示意图如下所示:

二叉树

二叉树是一种特殊的顺序树,它有左右两个孩子子树,即左右孩子顺序不能替换。二叉树的结点数为大于0小于等于2。常见的二叉树结构如下:

二叉树的性质

性质1 在二叉树的第i层上至多有个结点(i>=1)
由数据归纳法即可证明,
i=1,结点数为1
i=2,结点数为2
i=3,结点数为4
i=4,结点数为8
I=n, 结点数为.
性质2 深度为K的二叉树至多有-1个结点(k >=1)
换言之,如果二叉树的深度确定,则其最大的结点数也是确定的。
证明(可以利用性质1)
深度为K的二叉树的结点个数=二叉树中每一层结点个数的总和。即为:
= 1 + 2 + 4 + 8 + … + =-1(等比公式)
性质3 二叉树中,终端结点个数与度为2的结点个数有如下关系:
N0= N2 + 1
性质4:结点数为n的完全二叉树,其深度为(向下取整)+ 1
由性质2及完全二叉树的定义有:
性质5:在按层序编号的n个结点的完全二叉树中,任意一个结点i()有:
(1) i = 1时,结点i是树的根,否则(i> 1),结点i的双亲为i/2(向下取整),如
,取i = 2.
(2) 2i > n时,结点i无左孩子,为叶结点,否则结点i的左孩子为结点2i
(3) 2i+1 > n时,结点i无右孩子,否则结点i的右孩子为结点2i +1.
性质6: 含有n个结点的二叉链表中,有n + 1个空链域。

点击复制链接 与好友分享!回本站首页
上一篇:Django第一弹之初见
下一篇:接口测试的总结
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站