二叉树 – 数据结构和算法43

二叉树

让编程改变世界

Change the world by program

二叉树的定义

世上树有万千种，唯有二叉课上讲。这里的二叉是二叉树，因为二叉树使用的范围最广，最具有代表意义，因此我们重点讨论二叉树。

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

这个定义显然是递归形式的，所以咱看上去有点晕，因为自古有“神使用递归，人使用迭代！”

二叉树的特点

每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。（注意：不是都需要两棵子树，而是最多可以是两棵，没有子树或者有一棵子树也都是可以的。）

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

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

二叉树的五种基本形态

空二叉树

只有一个根结点

根结点只有左子树

根结点只有右子树

根结点既有左子树又有右子树

二叉树很二

小甲鱼为什么这么说呢？因为若只从形态上来考虑，拥有三个结点的普通树只有两种情况：两层或者三层。

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

特殊二叉树

因为他很二，所以他也很特殊。小甲鱼接下来再介绍一下一些特殊的二叉树，虽然暂时你可能不能理解它们的用处，但我们有必要先了解一下。

斜树

顾名思义，斜树是一定要斜的，但斜也要斜得有范儿，例如：

满二叉树

坡坡有云：“人有悲欢离合，月有阴晴圆缺，此事古难全。但愿人长久，千里共长娟。”意思就是说完美的那是理想，不完美的才是人生。

但是对于二叉树来说，是否存在完美呢？有滴，那就是满二叉树啦。

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

不理解？No pic you say a J8….

满二叉树的特点有：

叶子只能出现在最下一层。

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

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

完全二叉树

满二叉树和完全二叉树历年都是一个重大考点，因为考生很容易混淆两者，但如果只是为了深入学习编程，那么只需要理解即可。记得我们曾说过：理解越多，需要记住的就越少！

对一棵具有n个结点的二叉树按层序编号，如果编号为i(1

完全二叉树的特点有：

叶子结点只能出现在最下两层。

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

倒数第二层，若有叶子结点，一定都在右部连续位置。

如果结点度为1，则该结点只有左孩子。

同样结点树的二叉树，完全二叉树的深度最小。

注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

以下这些都不是完全二叉树：

二叉树的性质

作为课后扩展作业，在不谷哥无度娘的条件下，自己完成：通过观察二叉树的图片，总结出你认为的二叉树应该具有的性质。

例如：在二叉树的第i层上至多有2^(i-1)个结点。

视频下载

备用视频下载
技术, IT技术, 数据结构和算法, 二叉树

                                                    风险提示及免责条款

市场有风险，投资需谨慎。本文不构成个人投资建议，也未考虑到个别用户特殊的投资目标、财务状况或需要。用户应考虑本文中的任何意见、观点或结论是否符合其特定状况。据此投资，责任自负。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！