前言
什么是树？
提到树(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个非叶结点
