【数据结构】二叉树的特性
💟作者简介：大家好呀！我是路遥叶子，大家可以叫我叶子哦！❣️
📝个人主页：【路遥叶子的博客】
🏆博主信息：四季轮换叶，一路招摇胜！专栏
【安利Java零基础】
【数据结构-Java语言描述】
🐋希望大家多多支持😘一起进步呀！~❤️
🌈若有帮助，还请【关注➕点赞➕收藏】，不行的话我再努力努力呀！💪
————————————————
⚡版权声明：本文由【路遥叶子】原创、在CSDN首发、需要转载请联系博主。
🍁想寻找共同成长的小伙伴，请点击【Java全栈开发社区】
目录
🐋二叉树的特性
🌲1）特性1：i层最多结点数 2^i
🌲2）特性2：最多结点个数 2^h-1
🌲3）特性3：叶子结点关系 n_0 = n_2 + 1
🌲 4）特性4：深度⌊log2n⌋+ 1
🌲5）特性5：判断是否
🐋小试牛刀
如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧~~~赶紧动起来，让我们一起加油学习吧！
想要了解更多吗？没时间解释了，快来点一点！
前言
什么是树？
提到树(Tree)，大家脑海中首先浮出的画面应该是类似这样的：
之所以我们会用“树”这个名词来命名具有“一对多关系”特性的数据结构，是因为树刚好能够很形象地诠释这种特性。
从上图树可以看出，它有一个树根，从树根开始往上分叉，主树干分叉成许多次树干，次树干又继续分叉为许多小树枝，小树枝上有许多叶子……主树干对次树干、次树干对小树枝、小树枝对叶子都是一对多的关系，那我们用圆圈代表树干和叶子，把自然界的树倒过来看进行一次抽象，就可得下图：
可以看到，现实中的树完美契合我们需要的数据结构，所以我们称这种数据结构为树(Tree)。既然知道了什么是树，那么我们今天就来聊聊树的特性都有那些！
💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚
🐋二叉树的特性
在讲解特性之前，先来了解一下，在二叉树中对结点层次和树的深度是如何定义吧！
| 结点的层次 | 规定树中根节点的层次为0，其他结点的层次是双亲结点的层次数加1，结点P层次数为4 |
| 树的深度 | 树中所有结点的层次数的最大值加1。 |
🌲1）特性1：i层最多结点数 2^i
-
二叉树中第i(i>=0)层上的结点数最多为2^i【2的i次方，i表示结点的层次】
🌲2）特性2：最多结点个数 2^h-1
-
深度为h(h>=1)的二叉树中最多有2^h-1个结点。【2的h次方-1，h表示树的深度】
由性质1可知，第i层上的最大结点树为2^i,那么我们只需要将每层的结点数相加，就可以得到树最多有多少个结点。
即可得到：深度为h的二叉树中结点的总数最多为2^0+2^1+2^3+......+2^h-1 = 2^h-1个。其实不能看出，树结点的总数计算，就是对2从0次方开始一直累加到2的h-1次方，在数学中其计算，就是一个对等比数列的求和。
等比数列还记得吗？下面我们一起来计算计算吧！
以上就是一个等比数列求和，化简之后得到的一个公式，我们将其代入，可得：
🌲3）特性3：叶子结点关系 n_0 = n_2 + 1
先来了解一些二叉树中对度的定义吧！
| 结点的度 | 该结点所拥有的子树的数目。 |
| 树的度 | 树中所有结点度的最大值。 |
| 叶结点 | 树中度为0的结点，也称为终端结点。 |
- 对于任意一颗二叉树，若其叶结点的个数为n_0，度为2的结点个数为n_2，则有n_0=n_2+1
-
验证1：
-
验证2：
-
证明 ：
🌲 4）特性4：深度⌊log2n⌋+ 1
-
具有n个结点的完全二叉树的深度为 ⌊log2n⌋ + 1 或 ⌊log2(n+1)⌋
- 数学常识
向下取整的运算称为Floor，用数学符号⌊ ⌋表示；向上取整的运算称为Ceiling，用数学符号⌈ ⌉表示
例如：
⌊59/60⌋=0
⌈59/60⌉=1
⌊-59/60⌋=-1
⌈-59/60⌉=0
⌊⌋ 表示向下取整。
⌈ ⌉表示向上取整
🌲5）特性5：判断是否
-
若对含n个结点的完全二叉树从上到下且从左至右进行0至n-1的编号，则对完全二叉树中任意一个编号为1的结点有：
-
若i=0，则该结点是二叉树的根，无双亲，否则编号为(i-1)/2的结点为其双亲结点。
-
若2i+1>=n，则该结点无左孩子，否则，编号为2i+1的结点为其左孩子结点
-
如果2i+2>=n，则该结点无右孩子结点，否则，编号为2i+2的结点为其右孩子结点。
-
二叉树的5个特性就介绍到此啦！快来检验一下成果吧！
💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️💙 💜 ❤️ 💚💙 💜 ❤️ 💚💙 💜 ❤️ 💚❤️
🐋小试牛刀
1、将含有83个结点的完全二叉树从根结点开始编号, 根为1号，后面按从上到下,从左到右的顺序对结点编号，那么编号为41的结点的双亲结点编号为( )。
A.42 B. 40 C. 21 D. 20
2、将含有62个结点的完全二叉树从根结点开始编号, 根为1号, 后面按从上到下,从左到右的顺序对结点编号，那么编号为26的结点的双亲结点编号为( )。
A.13 B. 12 C. 21 D. 20
3、一颗完全二叉树的结点个数为 100，从0开始自上而下、自作至右的顺序对结点进行连续编号，则第 60 个结点的度为（ ）。
A.0 B.1 C.2 D.不确定
4、一棵满二叉树的结点个数为n，高度为h，则n=( ) 。
A. 2h-1 B.2h+1 C.2h -1 D. 2h+1
5、假设只有1个结点的二叉树的深度为1，具有256个结点的完全二叉树的深度为()。D
A. 6 B.7 C.8 D.9
6、若对含 n 个结点的完全二叉树从上到下且从左至右进行 0至 n-1 的编号，则对完全二叉树中任意一个编号为 i 的结点，以下正确的是（ ）。
A. 编号为(i-1)/2的结点为其双亲结点。
B. 编号为 2i+1 的结点为其左孩子结点。
C. 该结点是层次遍历时访问的第i+1个结点（规定根结点为第一个访问到的结点）。
D. 以上都不正确。
6、一棵哈夫曼树共有 n 个非叶结点，则该树一共有（ ）个结点。
A. 2*n-1 B. 2*n +1 C. 2*n D. 2*(n-1)
7、对于一颗有 n 个结点、度为 4 的树来说，（ ） 。
A．树的高度最多为 n-3
B．树的高度最多为 n-4
C．第 i 层上最多有 4(i-1)个结点
D．至少在某一层上正好有 4 个结点
8、对于一棵高度为h、度为4的树来说，（ ） 。
A．至少有h+3个结点
B．至多有4h-1个结点
C．至多有4h个结点
D．至少有h+4个结点
9、对于一颗有50个结点的，度为3的树来说，其最小高度为（ ） 。
A．3 B．4 C．5 D．6
10、 一棵有20结点的二叉树，其2度结点数的个数为8，则该树共有（ ）个1度结点。 B
A. 2 B. 3 C. 4 D. 5
1、深度为5的完全二叉树第5层上有4个结点，该树一共有19个结点
2、深度为5的完全二叉树共有20个结点，则第5层上有5个结点(根所在结点为第一层)
3、一棵哈夫曼树共有n个非叶结点，则该树有n+1个叶节点
4、一棵哈夫曼树有n个叶子结点（终端结点），该树总共有2n-1个结点
5、一棵哈夫曼树总共有23个结点，该树共有12个叶结点（终端结点）
6、一棵完全二叉树共有30个结点，则该树一共有5层(根结点所在层为第一层)
7、一棵完全二叉树共有5层，且第5层上有六个结点，该树共有21个结点
8、一棵有n个结点采用链式存储的二叉树，则该树共有n+1个指针域为空
9、在一棵二叉树中，若编号为i的结点存在右孩子，则右孩子的顺序编号为2i+1
10、一棵哈夫曼树共有n个叶结点，则该树有n-1个非叶结点
你回答对了几题？距离100分还差多少呢？
赶快了练习练习吧，我们一起加油！棒棒哒！
如果文章对您有帮助，就拿起小手赶紧给博主点赞💚评论❤️收藏💙 一下吧~~~赶紧动起来，让我们一起加油学习吧！
想要了解更多吗？没时间解释了，快来点一点！
路遥叶子的博客_CSDN博客-数据结构,安利Java零基础,spring领域博主路遥叶子擅长数据结构,安利Java零基础,spring,等方面的知识https://blog.csdn.net/zsy3757486?spm=1010.2135.3001.5343