数据结构笔记——二叉树的定义和性质

获取更多精彩内容&＃xff0c;您还可以关注我的微信公众号——Android机动车。

在一些电视节目中&＃xff0c;会猜测商品价格&＃xff0c;有的人是一点一点的数字累加&＃xff0c;这样的策略效率太低了。其实有一种经典的折半查找算法&＃xff0c;就类似于我们今天要说的二叉树。

二叉树定义

二叉树&＃xff1a;是n&＃xff08;n>&＃61;0&＃xff09;个结点的有限集合&＃xff0c;该集合或者为空集&＃xff08;称为空二叉树&＃xff09;&＃xff0c;或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

如下图就是一个二叉树&＃xff1a;

二叉树特点

二叉树的特点有&＃xff1a;

每个结点最多两个子树&＃xff0c;所以二叉树中不存在度大于2的结点。注意不是只有两棵子树&＃xff0c;而是最多有。没有子树或者有一棵子树都是可以的。
左子树和右子树是有顺序的&＃xff0c;次序布恩那个任意颠倒。
即使树中的某结点只有一棵子树&＃xff0c;也要区分它是左子树还是右子树。如图&＃xff1a;树1和树2是同一棵树&＃xff0c;但却是不同的二叉树。

二叉树具有五种基本形态&＃xff1a;

空二叉树&＃xff1b;
只有一个根结点&＃xff1b;
根结点只有左子树&＃xff1b;
根结点只有右子树&＃xff1b;
根结点既有左子树又有右子树。

特殊二叉树

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

1、斜树

顾名思义&＃xff0c;斜树一定是斜的&＃xff0c;但是往那边斜还是有讲究的。

所有的结点都只有左子树的二叉树叫左斜树&＃xff0c;所有结点都是只有右子树的二叉树叫右斜树。两种统称为斜树。

下面两个图分别就是左斜树和右斜树&＃xff1a;

2、满二叉树

苏东坡有诗云&＃xff1a;人有悲欢离合&＃xff0c;月有阴晴圆缺&＃xff0c;此事古难全。意思就是完美是理想&＃xff0c;不完美才是人生。

我们通常看到的例子全是左高右低、参差不齐的二叉树&＃xff0c;是否有完美的二叉树呢。

在一棵二叉树中&＃xff0c;如果所有分支结点都存在左子树和右子树&＃xff0c;并且所有的叶子结点都在同一层上&＃xff0c;这样的二叉树叫做满二叉树。如图

单单是每个结点都有左右子树&＃xff0c;不能算是满二叉树&＃xff0c;还必须要所有的叶子结点都处在同一层&＃xff0c;这样就做到了二叉树的平衡。因此满二叉树的特点有&＃xff1a;

叶子只能出现在最下面一层&＃xff0c;出现在其他层就不能达到平衡&＃xff1b;
非叶子结点的度一定是2&＃xff1b;
同样深度的二叉树中&＃xff0c;满二叉树的结点个数最多&＃xff0c;叶子树最多。

3、完全二叉树

**对一棵具有n个结点的二叉树按层序编号&＃xff0c;如果编号为i&＃xff08;1<&＃61;i<&＃61;n&＃xff09;的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同&＃xff0c;则这棵二叉树称为完全二叉树。**如图&＃xff1a;

首先要从字面上区分&＃xff0c;“完全”和“满”的差异&＃xff0c;满二叉树一定是完全二叉树&＃xff0c;完全二叉树不一定是满的。

注意完全二叉树中的编号与满二叉树中的相同&＃xff0c;而且编号全部连续&＃xff0c;有断开的就不是完全二叉树&＃xff0c;如下图中的三棵树都不是完全二叉树。

完全二叉树的特点&＃xff1a;

叶子结点只能出现在最下面两层&＃xff1b;
最下层的叶子一定集中在左部连续位置&＃xff1b;
倒数二层&＃xff0c;若有叶子结点&＃xff0c;一定都在右部连续位置&＃xff1b;
如果结点的度为1&＃xff0c;则该结点只有左孩子&＃xff0c;即不存在只有右子树的情况&＃xff1b;
同样结点数的二叉树&＃xff0c;完全二叉树深度最小。

我们也得出一个判断某二叉树是否是完全二叉树的方法&＃xff0c;那就是看着树的示意图&＃xff0c;心中默默给每个结点按照满二叉树的结构逐层顺序编号&＃xff0c;如果编号出现空挡&＃xff0c;就说明不是完全二叉树&＃xff0c;否则就是。

二叉树的性质

二叉树有一些需要理解并记住的特性&＃xff0c;便于更好地使用它。

二叉树性质1

在二叉树的第i层上至多有2^i-1个结点&＃xff08;i>&＃61;1&＃xff09;。

上图中&＃xff1a; 第1层&＃xff1a; 1个&＃xff1a; 2^1-1&＃61;2⁰&＃61;1 第2层&＃xff1a; 1个&＃xff1a; 2^2-1&＃61;2¹&＃61;2 第3层&＃xff1a; 1个&＃xff1a; 2^3-1&＃61;2²&＃61;4 第4层&＃xff1a; 8个&＃xff1a; 2^4-1&＃61;2³&＃61;8

通过数据归纳法&＃xff0c;很容易得出在二叉树的第i层上最多有 2^i-1个结点。

二叉树性质2

深度为k的二叉树最多有2^k-1个结点&＃xff08;k>&＃61;1&＃xff09;。

这里注意是2的k次幂再减1。

如果有一层&＃xff0c;最多1&＃61;2¹-1个结点如果有两层&＃xff0c;最多1&＃43;2&＃61;2²-1个结点如果有三层&＃xff0c;最多1&＃43;2&＃43;4&＃61;2³-1个结点如果有四层&＃xff0c;最多1&＃43;2&＃43;4&＃43;8&＃61;2⁴-1个结点

通过数据归纳法的论证&＃xff0c;可以得出如果有k层&＃xff0c;结点数最多为2^k-1。

二叉树性质3

对任何一棵二叉树T&＃xff0c;如果其终端结点数为n₀&＃xff0c;度为2的结点数为n₂&＃xff0c;则n₀&＃61;n₂&＃43;1。

终端结点就是叶子结点&＃xff0c;而一棵二叉树&＃xff0c;除了叶子结点外&＃xff0c;剩下的就是度为1和2的结点了&＃xff0c;设n₁是度为1的结点数。则树T的结点总数就是n&＃61;n₀&＃43;n₁&＃43;n₂。

我们换个角度&＃xff0c;再数一数连接线&＃xff0c;由于根结点只有分支出去&＃xff0c;没有分支进入&＃xff0c;所以分支线总数为结点总数减去1&＃xff0c;n-1&＃61;n₁&＃43;2n₂&＃xff0c;又因为n&＃61;n₀&＃43;n₁&＃43;n₂&＃xff0c;得出n₀&＃61;n₂&＃43;1 。