二叉树的五大性质及证明「建议收藏」

二叉树的五大性质及证明「建议收藏」二叉树(BinaryTree)定义:一棵二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)五种形态: 1.性质1性质1 在二叉树的第i层至多有2^(i-1)个结点。(i>=1) [用数学归纳法证明]  …

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

二叉树(Binary Tree)

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

特点:每个结点至多只有两棵子树(二叉树中不存在度大于2的结点)

五种形态

二叉树的五大性质及证明「建议收藏」

 

1. 性质1

性质1  在二叉树的第 i 层至多有 2^(i -1)个结点。(i>=1)

 

[用数学归纳法证明]

       证明:当i=1时,只有根结点,2^(i -1)=2^0=1。

       1) 设:对所有j,i>j>=1,命题成立,即第j层上至多有2^(j-1)个结点。

       2) 由归纳假设第i-1层上至多有2^(i-2)个结点。

       3) 由于二叉树的每个结点的度至多为2,故在第i层上的最大结点数为第i-1层上的最大结点数的2倍,即2* 2^(i-2)= 2^(i-1) 

证毕。

              

 

2. 性质2

性质2  深度为 k 的二叉树至多有 2^(k-1)个结点(k >=1)。

       证明:由性质1可见,深度为k的二叉树的最大结点数为 

二叉树的五大性质及证明「建议收藏」

 

3. 性质3

性质3  对任何一棵二叉树T, 如果其叶结点数为n0, 度为2的结点数为 n2,则n0=n2+1。

       证明:若度为1的结点有 n1个,总结点个数为n,总边数为 e,则根据二叉树的定义,

            n = n0 + n1 + n2    

            e = 2n2 + n1 = n – 1 (除了根节点,每个节点对应一条边 )

           因此,有  2n2+ n1 =n0 + n1 + n2- 1

                          n2= n0 – 1  =>   n0= n2+ 1

          空链域:2n0+ n1 = n0 + n2 +1+ n1 = n+1

 

4. 性质4

性质4  具有 n (n>=0) 个结点的完全二叉树的深度为二叉树的五大性质及证明「建议收藏」+1   

       证明:设完全二叉树的深度为 h,则根据性质2 和完全二叉树的定义有

            2^(h-1)- 1 < n <= 2^h – 1或 2^(h-1)<= n < 2^h

               取对数 h-1 < log2n  <= h,又h是整数,

               因此有 h = 二叉树的五大性质及证明「建议收藏」+1 

 

5. 性质5

性质5  如将一棵有n个结点的完全二叉树自顶向下,同层自左向右连续为结点编号0,1, …, n-1,则有: 

       1)若i = 0, 则 i 无双亲,   若i > 0, 则 i 的双亲为」(i -1)/2」

       2)若2*i+1 < n, 则i 的左子女为 2*i+1,若2*i+2 < n, 则 i 的右子女为2*i+2

       3)若结点编号i为偶数,且i != 0,则左兄弟结点i-1.

       4)若结点编号i为奇数,且i != n-1,则右兄弟结点为i+1.

       5)结点i 所在层次为」log2(i+1) 」

 

 

参考资料:

1. Boss的PPT

 

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

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

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

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

(0)
blank

相关推荐

发表回复

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

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