二叉树性质及部分通俗解释

vlambda
2020-02-05

二叉树性质及部分通俗解释

学习数据结构和算法的时候，树是一种非常重要的数据结构，并且在各种语言中的应用也十分广泛。

为什么要学习二叉树？

二叉树是一种基础的“树”，许多树都是以二叉树为基础衍化而来的，所以学习二叉树非常有必要。

为什么要掌握树的性质？

掌握树的性质，对于使用树解决实际问题是非常有必要的。

下边会分为两个版本去证明二叉树的4个重要性质：

性质1：在二叉树的第i层上，至多有2ⁱ⁻¹个节点。

数学证明方法：

假设：第i层的结点至多为 N, 由上需证明在二叉树的第i层上有N=2ⁱ⁻¹

① i=1时，因为二叉树只有一层时只有一个根结点，故 2⁰=1 成立

② 假设，当 i =k 时，等式成立，即N=2^k−1

那么，当 i =k +1 时，因为第 k+1 层是第 k 层的下一层，故第 k + 1 层的结点最多为

2^k−1∗2=2^k=2^(k+1)−1, 即当i = k + 1时，N=2^(k+1)−1成立,

由①, ②可知对一切自然数 i 等式成立

通俗解释：

①二叉树的根节点必定是一个，所以根节点符合此性质；

②二叉树配合国家二孩政策，最多生二胎，不超生，也就是说每个节点最多有两个子节点，那么下一层的个数，撑死了也就是上一层的二倍，故性质成立。

特性2:深度为 h 的二叉树, 它的结点至多为2^h−1 (深度即层数)

数学证明：

设，深度为 h 的二叉树的结点至多为 S(h),需证明等式S(h)=2h−1成立

二叉树，每一层都取最大的结点数，由特性1 有：

2⁰+2¹+2²+...+2^h−1 = S(h) ①

2¹+2²+2³+...+2^h= 2S(h) ②

② - ① = 2S(h) - S(h) = S(h) = 2^h−2⁰=2^h−1，即等式S(h)=2^h−1成立

通俗解释：

无。

特性3:对任何一颗二叉树，若它含有n₀个叶子结点，n₂个度(度，即产生分支数目)为2的结点，则必存在关系式:n₀=n₂+1

设，度为0的结点个数为 n0, 度为1的结点个数为n1, 度为2的结点个数为n2, 整个二叉树上结点的数目为 n，二叉树上分支的数目为 b,

则有n₀+n₁+n₂=n①

除了根结点以外都有一双亲结点(也叫父结点)，有一个双亲,说明有一个分支

分支数目为 b，根节点没有父节点。

所以 n=b+1②

那么分支都是由度不为0的结点产生的，度为0的产生0个分支，度为1的结点产生1个分支，度为2的结点产生2个分支。

因为二叉树的结点数等于分支数+1，故有：n₁+2n₂+1=n ③

由 ①−③=n₀−n₂−1=0 即， n₀=n₂+1

通俗解释：

二叉树性质及部分通俗解释

由上图我们看到，只有根节点有两个度n₂，是符合n₀=n₂+1，n₀也只有两个，那么我们任意加一个结点会发生什么，我们思考一下？

对，那就是会多一个n₂，同时也会多一个n_0；

这个时候有同学就会说了，那我加两个呢，你这还成立吗？

同样的，多一个n₂，同时也会多一个n_0，中间的那个就变成n₁了_；

这次先介绍到这里！

再见~

vlambda博客
学习文章列表