鱼C论坛

 找回密码
 立即注册
查看: 8882|回复: 24

[学习笔记] ★ 第四十三讲 二叉树 | 【数据世界的2X青年】★

[复制链接]
发表于 2017-11-3 14:03:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x

                               
登录/注册后可看大图


    


用一节课的时间,提高生活幸福感

------小甲鱼


欢乐傻笑并存

智慧邪恶同在


笔记内涵------





二叉树的定义


世上树有万千种,唯有二叉课上讲。

这里的“二叉”是二叉树,因为二叉树使用的范围最广,最具有代表意义,因此我们重点讨论二叉树。

定义:
        二叉树(Binary Tree)是n(n>=0)个结点的有限集合,该集合或者为空集(空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。


这个定义显然是递归形式的,所以咱看上去有点晕。

因为自古有云:
        “神使用递归,人使用迭代!

Snip20171103_19.png





二叉树的特点


每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。

注意:
        不是都需要两棵子树,而是最多可以是两棵,没有子树或者有一棵子树也都是可以的。


左子树和右子树是有顺序的,次序不能颠倒。

即使树中某结点只有一棵子树,也要区分它是左子树还是右子树,下面是完全不同的二叉树:
Snip20171103_20.png





五种基本形态


Snip20171103_29.png
空二叉树

Snip20171103_30.png
只有一个根结点


Snip20171103_31.png
根结点只有左子树


Snip20171103_32.png
根结点只有右子树


Snip20171103_33.png
根结点既有左子树又有右子树





很二的二叉树


为什么这么说呢?

因为若只从形态上来考虑,拥有三个结点的普通树只有两种情况:
        两层或者三层。


但对于很二的二叉树来说,由于要区分左右,所以就演变成五种形态
Snip20171103_22.png





特殊二叉树-斜树


因为他很二,所以他也很特殊。

接下来再介绍一下一些特殊的二叉树

虽然暂时你可能不能理解它们的用处,但我们有必要先了解一下。

斜树:
        斜树是一定要斜的,但斜也要斜得有范儿。

例如:
Snip20171103_23.png





特殊二叉树-满二叉树


坡坡有云:
        “人有悲欢离合,月有阴晴圆缺,此事古难全。但愿人长久,千里共长娟。”


意思就是说:
        完美的那是理想,不完美的才是人生


但是对于二叉树来说,是否存在完美呢?

有滴,那就是满二叉树啦。




满二叉树 VS 完全二叉树


在一棵二叉树中,如果所有分支结点都存在左子树和右子树。

并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

例如:
Snip20171103_24.png


满二叉树的特点有:
        ◊叶子只能出现在最下一层。

        ◊非叶子结点的度一定是2。

        ◊在同样深度的二叉树中,满二叉树的结点个数一定最多,同时叶子也是最多。


满二叉树和完全二叉树历年都是一个重大考点,因为考生很容易混淆两者。


完全二叉树定义:
对一棵具有n个结点的二叉树按层序编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点位置完全相同


例如:
Snip20171103_25.png


完全二叉树的特点有:
        &#9674;叶子结点只能出现在最下两层。

        &#9674;最下层的叶子一定集中在左部连续位置。

        &#9674;倒数第二层,若有叶子结点,一定都在右部连续位置。

        &#9674;如果结点度为1,则该结点只有左孩子。

        &#9674;同样结点树的二叉树,完全二叉树的深度最小。


二者考试重点:
        满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。


以下这些都不是完全二叉树:
Snip20171103_28.jpg
Snip20171103_27.png
Snip20171103_26.png





课后作业


二叉树性质:
游客,如果您要查看本帖隐藏内容请回复






这位鱼油,如果喜欢本系列笔记,请订阅 专辑&#9758;传送门)(不喜欢更要订阅

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2018-5-2 19:32:27 | 显示全部楼层
了解了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2018-5-4 10:35:50 | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-2-13 11:02:14 | 显示全部楼层
二叉树的性质,第二个错了应该是2的K次方-1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-2-14 14:55:21 | 显示全部楼层
1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-2-16 15:31:24 | 显示全部楼层
1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-4-17 21:04:44 From FishC Mobile | 显示全部楼层
谢谢啦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-11-16 15:31:47 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-12-4 17:36:19 | 显示全部楼层
{:5_109
:}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-2-24 13:05:58 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-6-23 11:48:33 | 显示全部楼层
学习一下
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-8-27 10:49:04 | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2020-11-12 16:52:59 | 显示全部楼层
瑞斯拜
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2020-11-12 22:43:54 | 显示全部楼层
hao
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-4-6 11:42:56 | 显示全部楼层
啊涂涂 发表于 2019-2-13 11:02
二叉树的性质,第二个错了应该是2的K次方-1

可能只是打不出来
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-4-6 15:20:38 | 显示全部楼层
1.证明:根据二叉树的性质,每个结点至多有两个子树,每层的最多数量从1,2,4,8一直递增,每层比前面一层的结点数至少多一倍,由此可知每层的结点数是单调递增的等比数列,由此可推出第i层的结点数为2的i-1次方。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2021-5-11 12:39:08 From FishC Mobile | 显示全部楼层
look
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-5-14 08:43:21 From FishC Mobile | 显示全部楼层
学习
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-5-17 22:16:28 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2021-12-9 18:24:41 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 19:54

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表