算法：二叉树的性质

淡淡的烟草味﹌ 2023-02-14 10:53 1阅读 0赞

# 性质一 #

**在二叉树的第i层上最多有2^(i-1)个节点（i>=1）**

证明：采用归纳法证明此性质

*  当i=1时，只有一个根节点，2^(i-1) = 2^(0) = 1，命题成立
 *  当j>1时， 由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目" 最多是 “第i层的结点数目的2倍”。也就是第(i+1)层节点数 = 2 \* 第i层节点数。
    
    >  *  f(n) = 2\*f(n-1).  
    >     f(1) = 1 = 2^(0)  
    >     f(2) = 2 \* f(1) = 2^(1)  
    >     f(3) = 2^(2)  
    >     f(i) = 2^(i-1)

# 性质二 #

**深度为k的二叉树最多有2^(k)-1个节点(k>=1)**

证明：深度为k的二叉树的所有节点为各层上的所有节点之和。

*  证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：  
    20+21+…+2k-1=2k-1  
    故原命题得证！

> 1 + 2 = 4 -1  
> 1 + 2 + 4 = 8 - 1  
> 1 + 2 + 4 + 8 = 16 - 1

# 性质三 #

性质3：包含n个结点的二叉树的高度至少为log2 (n+1)

证明：根据"性质2"可知，高度为h的二叉树最多有2\{h\}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

# 性质四 #

**对任何一颗二叉树，如果其终端节点数为n0，度为2的节点数为n2，那么n0=n2+1**

证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)=“0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)”。由此，得到等式一。  
(等式一) n=n0+n1+n2

令一方面，0度节点没有孩子，1度节点有一个孩子，2度节点有两个孩子，因为二叉树孩子节点的数量数n0 + 2\*n2，故二叉树中的结点总数又可表示为等式二。  
(等式二) n=n1+2 \* n2+1

既有：n0+n1+n2 = 0 + n1 + 2\*n2 + 1 ====》 n0 = n2 + 1

发表评论取消回复

表情：

评论列表（有 0 条评论，1人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构--二叉树的性质

二叉树二叉树的性质性质1 性质2 性质3 性质4 性质5 二叉树的性质性质1

旧城等待，/ 2023年02月22日 10:43/ 0 赞/ 22 阅读

相关算法：二叉树的性质

性质一在二叉树的第i层上最多有2^(i-1)个节点（i>=1）证明：采用归纳法证明此性质当i=1时，只有一个根节点，2^(i-1) = 2^(0) = 1

淡淡的烟草味﹌/ 2023年02月14日 10:53/ 0 赞/ 2 阅读

相关二叉树的概念与性质

`本文主要为观看哔哩哔哩视频网站上的王道考研的数据结构的学习笔记，如有侵权，请联系我删除` 二叉树的定义 ![在这里插入图片描述][watermark_type_ZmF

╰半夏微凉°/ 2023年01月07日 13:28/ 0 赞/ 178 阅读

相关二叉树的定义、性质、存储

二叉树的定义二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查

布满荆棘的人生/ 2022年09月26日 01:53/ 0 赞/ 154 阅读

相关二叉树的性质

性质1:对于任何一棵二叉树T,如果其终端结点数为N0,度为2的结点数为N2,则N0=N2+1,如下图: ![20150414171814322][] 性质2:深度为K的二叉

你的名字/ 2022年08月07日 13:56/ 0 赞/ 160 阅读

相关二叉树的性质总结

性质1：在二叉树的第i层至多有![Center][]个结点性质2：深度为K的二叉树的最大节点数为(k>=1) ![20150904220459657][]

末蓝、/ 2022年08月04日 15:40/ 0 赞/ 171 阅读

相关二叉树的性质

二叉树概述在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树

叁歲伎倆/ 2022年07月18日 04:30/ 0 赞/ 157 阅读

相关二叉树的一些性质

在介绍二叉树性质之前，先谈一下二叉树的度与深度区别：二叉树的度：子树就是二叉树的分支。度就是分支的数目。没有分叉的二叉树节点的度就是0度。如果一个节点只有一个分叉就是1度。

ゝ一纸荒年。/ 2022年06月11日 07:37/ 0 赞/ 215 阅读

相关树的术语、二叉树的性质、二叉树的基本操作总结

一、树的术语 <table style=""> <tbody> <tr> <td style="border:1px solid rgb(211,

傷城~/ 2022年06月09日 04:06/ 0 赞/ 213 阅读

相关满二叉树、完全二叉树和完美二叉树的性质

满二叉树所有非叶子结点的度都是2，也就是说，一个结点要么没有孩子，要么就有两个孩子。 ![满二叉树][70] 完全二叉树除了叶子结点这一层外，其他各层结点

深藏阁楼爱情的钟/ 2022年05月29日 11:54/ 0 赞/ 259 阅读