树是一个程序中算是很难的知识点了，up在这里讲解一下，希望能帮助大家（打字辛苦，点一个免费的赞吧）

认识树结构

树结构呢有很像下面的图片一样，由主干到分支

接下来我们在了解一下树

结点就是树中的每一个元素：1,2,3,4,5,6,7,8

根节点就是整棵树的起始结点：1

子树可以看成整棵树中的小树，比如2,5,6就是整棵树的小树即子树

 

然后呢我们在认识一下树的概念。

比如在整棵树中1是根节点，而2,5,6这个小树的根节点则是2.

度：1.比如1的度为3，即2,3,4。    再比如2的度为2，即5,6。      

       2.像5,6,3,8这种没有度的结点，我们称之为叶结点。     

       3.那这个数的度为多少？我们依照第3点可以看出，这棵树结点最多的是1，有3个度，所以这棵树的度就为3。

深度：这个就很好理解了，从上往下数，分别有125 (3),126 (3)，13 (2),1478 (4)，而1478的层次是最多的，所以这棵树的深度就是4

学到这里，你已经掌握了关于树的基本结构。加油，继续看下去

接下来是重点内容——二叉树

二叉树即BT树，额，还真就很形象呢

空二叉树：没有任何结点

上面的内容还是比较简单的，现在我们再来看看二叉树的特点

我们来验证一下

第一行：结点数=2^(1-1)=2^0=1

第二行：结点数=2^(2-1)=2^1=2

第三行：结点数=2^(3-1)=2^2=4

第四行：结点数=2^(4-1)=2^3=8

。。。

综上所述在二叉树的第i层最多有2^(i-1)

所以我们的结果是对的

我们再来看看第二个特点（公式）

老样子，没有验证怎么可以直接说出来呢？

深度为k这里我们来看一下以下4种情况：

1.当k=1时：节点个数=2^1-1=1

2.当k=2时：节点个数=2^2-1=3

3.当k=3时：节点个数=2^3-1=7

4.当k=4时：节点个数=2^4-1=15

这里我们也是可以得出这个结论是正确的的：

即深度为k的二叉树至多有2^k-1个节点

最后我们再来看二叉树的第3个特点：

即：

所以以上3个特点有两个公式需要记忆：

1.在二叉树的第i层最多有2^(i-1)

2.深度为k的二叉树至多有2^k-1个节点

然后我们也要认识满二叉树，懂得满二叉树的运用及判断。

没想到吧，又学完一个知识点了最后我们来学习

完全二叉树

接着上面，我们再来看二叉树的第4个特点——完全二叉树

像下面这些也属于完全二叉树：

也就是说除最后一层以外的，这棵树必须是满二叉树。

就像上面的图一样除8,9,10,11,12||8,9,10,11,12,13||8,9,10,11以外都是满二叉树，对不对？

那最后一句话“在最后一层上只缺少右边的若干结点”是什么意思呢？

我们来看看错误完全二叉树的示例吧！

图一错误点：根据我们完全二叉树的定义除最后一层外,每一层上的结点数均达到最大值可以    判断这是错的（除6,7以外，3下面没有子节点应该是错的）正确来说应该在3下面多加一个左孩子和一个右孩子。

图二错误点：虽然它第一个条件满足了，但是第二个条件在最后一层上只缺少右边的若干结点却没有满足，那个6不应该出现在右边的，如果6是3的左孩子的话，那就对了。

总结：

完全二叉树应该满足以下两个特征：

1.除最后一层外，每一层上的结点数均达到最大值。

2.在最后一层上只缺少右边的若干结点。

接下来我们来练习一下吧

练一练

第一题

思考一下。

答案是 A

你答对了吗？

解答：套公式！深度为k的二叉树至多有2^k-1个节点

所以答案为：2^5-1=31，所以答案是A

第二题

思考一下

答案选B

你答对了吗？

解答：老样子套公式！谁的2次方-1最接近61？6！

2^6-1=61所以答案为6！

尾声：

二叉树的基本知识你已经掌握的差不多了

up会持续更新关于二叉树的知识，大家记得关注哦

再见了！

感谢观看