【数据结构与算法】初识二叉树(上)

✨hello，进来的小伙伴们，你们好耶！✨

🚎🚎系列专栏：【数据结构与算法】

⛵⛵本篇内容：二叉树相关知识点介绍！

⛴️⛴️作者简介：一名双非本科大三在读的Java编程小白，有个大厂梦，希望在合适的时间里，我们顶峰相见！

🚖🚖码云存放常仓库gitee：数据结构初阶: Java初阶数据结构学习全部代码存放！

 

一、树形结构

✈️✈️1、树的概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

🍛1、有一个特殊的结点，称为根结点，根结点没有前驱结点。
🍰2、除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继。
🍒3、树是递归定义的（非常重要）。

 🚀🚀注意：

1、树形结构中，子树之间不能有交集，否则就不是树形结构。

2、除了根节点外，一个节点只能有一个父节点，否则就不是二叉树。

3、一颗n个节点的树有n-1条边。

🚞🚞2、重要结论

1、结点的度：一个结点含有子树的个数称为该结点的度； 如上图：A的度为2。
2、树的度：一棵树中，所有结点度的最大值称为树的度； 如上图：树的度为2。
3、叶子结点或终端结点：度为0的结点称为叶结点； 如上图：H、I、J、K...等节点为叶结点。
4、双亲结点或父结点：若一个结点含有子结点，则这个结点称为其子结点的父结点； 如上图：A是B的父结点。

5、孩子结点或子结点：一个结点含有的子树的根结点称为该结点的子结点； 如上图：B是A的孩子结点。
5、根结点：一棵树中，没有双亲结点的结点；如上图：A。
7、结点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推。
8、树的高度或深度：树中结点的最大层次； 如上图：树的高度为4。

二、二叉树

🍊🍊1、概念

一棵二叉树是结点的一个有限集合，该集合：
1. 或者为空。
2. 或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。

🍎🍎结论：

1. 二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

对于任意的二叉树都是由以下几种情况复合而成的：

 🍱🍱二、两种特殊的二叉树

🍖🍖 1. 满二叉树: 一棵二叉树，如果每层的结点数都达到最大值，则这棵二叉树就是满二叉树。也就是说，如果一棵二叉树的层数为K，且结点总数是 ，则它就是满二叉树。

🍻🍻满二叉树：

🍺🍺2. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 

🍶🍶完全二叉树：

 🍍🍍三、二叉树的性质

1. 若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有2(i-1)个结点。括号里面代表的是次方。
2. 若规定只有根结点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 2(k) - 1个节点。
3. 对任何一棵二叉树, 如果其叶子结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1。

(这一条根据N个节点的二叉树有N-1条边很容易可以推理出来。)

4. 具有n个结点的完全二叉树的深度k为log2(n+1)向上取整，根据结论2就可以推导出来。

🌯🌯四、二叉树选择题练习

🍯1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（B ）
A 不存在这样的二叉树
B 200
C 198
D 199

解答：由结论3直接得出答案。

🍼2.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ A）
A n
B n+1
C n-1
D n/2

解答：这题分为两种情况，因为题目给出的是完全二叉树，而完全二叉树最后一个节点要么是叶子节点，要么是只有左孩子节点，也就是只有一个节点，那么前者二叉树的个数肯定是个奇数，后者二叉树的个数肯定是个偶数，因为有个根节点是单数，我们在多一个左孩子出来，那么结果肯定是偶数。

<节点数为偶数的情况下，叶子节点数为N/2。

<节点数为奇数的情况下，叶子节点数为N/2向上取整。

🥝3.一个具有767个节点的完全二叉树，其叶子节点个数为（B）
A 383
B 384
C 385
D 386

解答：根据上题结论，这题直接奇数/2向上取整得出结果为B。

🍞4.一棵完全二叉树的节点数为531个，那么这棵树的高度为（B ）
A 11
B 10
C 8
D 12

解答：由结论4便可以直接得出答案，注意结果向上取整。

OK，二叉树上篇的内容就到这里了，本次二叉树的知识点博主准备分为3篇来写，感谢大家的阅读，还希望小伙伴们一键三连，我们下篇见！