说在前面的话
欢迎来到我的博客！
在这里博主恭喜大家已经完成的线性表等数据结构的学习，今天咱们正式进入二叉树的一个大章节的。在这个章节里，我们的学习难度会有一个跃升。但是我相信，跟着博主的步伐学习，我们一定可以轻松学懂！
在这里，博主附上咱们数据结构学习的一个专栏，如果前面的知识还有不明白的伙伴们，可以先食用专栏哦！
- 手撕数据结构
文章目录
博主给大家的话
那么这里博主先安利一下一些干货满满的专栏啦！
数据结构专栏：手撕数据结构 这里包含了博主很多的数据结构学习上的总结，每一篇都是超级用心编写的，有兴趣的伙伴们都支持一下吧！
算法专栏：算法 这里可以说是博主的刷题历程，里面总结了一些经典的力扣上的题目，和算法实现的总结，对考试和竞赛都是很有帮助的！
力扣刷题专栏：跟着博主刷Leetcode 想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴，这里面都是博主的刷题记录，希望对你们有帮助！
C的深度解剖专栏：C语言的深度解剖 想要深度学习C语言里面所蕴含的各种智慧，各种功能的底层实现的初学者们，相信这个专栏对你们会有帮助的！
树和树的相关概念
朋友们，这就是树。
当然，这不是我们要学习的树，这是我们要学习的树
- 在这个图中我们可以看到，每一棵树，都可以划分成很多子树。然后每一棵子树，同样，可以划分为多棵树，所以树是递归定义的！这其实就是分治算法的核心思想。
树的一些相关概念
- 节点的度：一个节点含有的子树的个数称为该节点的度
- 叶节点或终端节点：度为0的节点称为叶节点
- 双亲节点：若一个节点含有子节点，则这个节点称为其子节点的父节点
- 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点
- 兄弟节点：具有相同父节点的节点互称为兄弟节点
- 树的度：一棵树中，最大的节点的度称为树的度
- 树的高度或深度：树中节点的最大层次（也就是有几层的意思）
- 堂兄弟节点：双亲在同一层的节点互为堂兄弟
- 节点的祖先：从根到该节点所经分支上的所有节点
- 子孙：以某节点为根的子树中任一节点都称为该节点的子孙
- 森林：由m（m>0）棵互不相交的树的集合称为森林
树的表示
树如果要存储数据，那可比线性表麻烦多了，我们在储存值的同时，我们还要体现节点和节点之间的关系。
我们比较容易想到的是这种定义方式：
但是问题是，一个节点是没有限定多少个孩子的，如果要这样搞，我们可以考虑用一个
vector
存我们的指针。
但是最优的定义方法：左孩子右兄弟法：
这种定义是什么意思呢，其实它可以很好的定义我们的树，如图：
看到这个图，我们应该就可以明白，这种定义方式的精妙之处了吧。
树结构的实际运用
我们的文件系统其实就是一棵多叉树。
如Linux的文件系统：
什么是二叉树
二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
特殊的一些二叉树
满二叉树
- 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是 说，如果一个二叉树的层数为K，且结点总数是2k-1 ，则它就是满二叉树。
完全二叉树
- 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。
二叉树的一些重要性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有2i-1个结点.
- 若规定根节点的层数为1，则深度为h的二叉树的最大结点数是2h-1.
- 对任何一棵二叉树, 如果度为0其叶结点个数为n0, 度为2的分支结点个数为n2,则有n0＝n2＋1
- 若规定根节点的层数为1，具有n个结点的满二叉树的深度，h=log2(n+1)
尾声
相信大家看到这里，已经对二叉树有了一定的了解了，当然，这只是最最基础的一些概念和性质，但同时它们也是最重要的，我们是必须要掌握的。如果你感觉这篇博客对你有帮助的话，别忘了一键三连再离开哦！
版权归原作者 #西城s 所有， 如有侵权，请联系我们删除。