数据结构完全二叉树性质

数据结构完全二叉树性质完全二叉树若二叉树左子树高度-右子树高度小于等于1且大于等于0则称该二叉树为完全二叉树。二叉树一般性质:性质1:二叉树第i层上的结点数目最多为2i−1(i≥1)2^{i-1}(i\geq1)2i−1(i≥1)性质2:深度为k的二叉树至多有2k−1(k≥1)2^{k-1}(k\geq1)2k−1(k≥1)个结点性质3:包含n个结点的二叉树的高度至少为log⁡2n+1\log_2n+1log2​n+1性质4:在任意一棵二叉树中,若叶子结点的个数为n0n_0n0​,度为2的结点数为n2n_2n

大家好,又见面了,我是你们的朋友全栈君。

完全二叉树

若二叉树左子树高度-右子树高度小于等于1且大于等于0则称该二叉树为完全二叉树。
二叉树一般性质:
性质1:二叉树第i层上的结点数目最多为 2 i − 1 ( i ≥ 1 ) 2^{i-1}(i \geq 1) 2i1(i1)

性质2:深度为k的二叉树至多有 2 k − 1 ( k ≥ 1 ) 2^{k-1}(k \geq 1) 2k1(k1)个结点

性质3:包含n个结点的二叉树的高度至少为 log ⁡ 2 n + 1 \log_2n+1 log2n+1

性质4:在任意一棵二叉树中,若叶子结点的个数为 n 0 n_0 n0,度为2的结点数为 n 2 n_2 n2,则 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1
性质4推导:
易知结点总数 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2,根据二叉树的度之和(边数量)=n-1,可得 n − 1 = n 0 ∗ 0 + n 1 ∗ 1 + n 2 ∗ 2 n-1=n_0*0+n_1*1+n_2*2 n1=n00+n11+n22
联合上面两个公式即可得到性质4
完全二叉树性质:
性质1:度为1的结点仅有1个或0个(叶子节点尽可能往左排)
性质2:叶子结点个数 = n 2 =\frac{n}{2} =2n = n + 1 2 =\frac{n+1}{2} =2n+1(n为奇数)
利用 n = n 0 + n 1 + n 2 n=n_0+n_1+n_2 n=n0+n1+n2 n 0 = n 2 + 1 n_0=n_2+1 n0=n2+1与性质1容易证明。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/138250.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号