【数据结构】树-二叉树-堆(上)

🍃 如果觉得本系列文章内容还不错，欢迎订阅🚩
🎊个人主页:小编的个人主页
🎀 🎉欢迎大家点赞👍收藏⭐文章
✌️ 🤞 🤟 🤘 🤙 👈 👉 👆 🖕 👇 ☝️ 👍

🐼前言

🌟在上一节我们实现了队列，如果感兴趣的小伙伴，可以阅读我的上一篇文章:> 队列，这一节小编给大家介绍一种非线性的数据结构：树

🐼树

✨树的概念:树是由根节点和若干颗子树构成的。树是一种非线性的数据结构，由一个集合以及在该集合上定义的一种关系构成。集合中的元素称为树的节点，因看起来像一颗倒挂的树，它的根朝上，尾叶子朝下。
🍂如图:

🐳树的结构:树有一个特殊的节点，根节点(A),该节点没有前驱节点，其余节点被分为互不相交的集合，每一个互不相交的集合又可以看作与树类似的子树。每一个结点只能有一个前驱节点，可以有0或多个后继节点。除了根节点外，每个节点有且仅有一个父节点。如果有n个节点，那么就有n-1条边注意:子树之间不能有交集，否则就构不成树结构
非树形结构:
🍂如图:

🐧树的相关术语

父结点/双亲结点：若⼀个结点含有子结点，则这个结点称为其子结点的父结点；如上图：A是B的父结点。
子结点/孩子结点：⼀个结点含有的子树的根结点称为该结点的子结点；如上图：B是A的孩子结点。
结点的度：⼀个结点有几个孩子，他的度就是多少；比如A的度为3，B的度为2，F的度为0。
树的度：⼀棵树中，最大的结点的度称为树的度；如上图：树的度为 3
叶子结点/终端结点：度为 0的结点称为叶结点；如上图： E，F，G…等结点为叶结点。
分支结点/非终端结点：度不为 0的结点；如上图： A，B，C，D…等结点为分支结点。
兄弟结点：具有相同父结点的结点互称为兄弟结点(亲兄弟)；如上图： E，F是兄弟结点。
结点的层次：从根开始定义起，根为第 1层，根的子结点为第 2层，以此类推。
树的高度或深度：树中结点的最大层次；如上图：树的高度为 3。
结点的祖先：从根到该结点所经分支上的所有结点；如上图： A是所有结点的祖先。
路径：⼀条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列；比如A到E的路径为：A-B-E；G到I的路径为:G-C-A-D-I.
子孙：以某结点为根的子树中任⼀结点都称为该结点的子孙。如上图：所有结点都是A的子孙。
森林：由 m（m>0）棵互不相交的树的集合称为森林；

🐳树的表示:由于树这个结构十分复杂，既要保存节点的数据，又要保持节点之间的关系。树的表示方法有很多，下面我们仅讨论，孩子兄弟表示法。
定义如下:

struct TreeNode
{
	struct TreeNode* child;//左边开始的第⼀个孩子节点
	struct TreeNode* brother;//指向其右边的下⼀个兄弟结点
	int data;
};

🍂如图:

🌻代码解析

child始终指向左边的第一个孩子，通过brother来找兄弟节点。这也就是左孩子右兄弟表示法。

🐼二叉树

🐳在上述描述的树型结构中，我们最常见的就是二叉树，⼀棵⼆叉树是结点的⼀个有限集合，该集合由⼀个根结点加上两棵别称为左子树和右子树的⼆叉树组成或者为空。
🍂如图:

二叉树具有以下特点:
1.二叉树不存在度大于2的节点。
2.叉树的子树有左右之分，次序不能颠倒，因此⼆叉树是有序树注意：对于任意的二叉树都是由以下几种情况复合而成的。
🍂如图:

现实中的二叉树

特殊的二叉树
🐳 满二叉树:满二叉树是每个节点都达到了最大值，也就是每个节点的度都为2，并且 如果高度为h，总结点个数为2^h-1个,h = log2 (n + 1)节点，那我们说它就是满二叉树。
🍂如图:

🐳完全二叉树:完全二叉树是效率很高的数据结构，满二叉树是一种特殊的完全二叉树。对于深度为K的，有 n个结点的二叉树，当且仅当其每⼀个结点都与深度为K的满⼆叉树中编号从 1至 n的结点⼀⼀对应时称之为完全二叉树。完全二叉树的节点个数要小于2^k-1个。
🍂如图:

二叉树的存储结构:
🐳二叉树一般有两种存储方式:顺序结构和链式结构。
顺序存储:顺序结构存储就是使用数组来存储，⼀般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。我们一般把堆(一种二叉树)用顺序存储的方式来存储。需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结构，⼀个是操作系统中管理内存的⼀块区域分段。
🍂如图:

链式存储
链式结构是用链表来实现二叉树的逻辑结构。通常链式结构有三个域:数据域和左右指针域，左右指针域分别指向左孩子和右孩子。链式结构还分为二叉链和三叉链。当前我们学习的是二叉链。
🍂如图:

🐼文末

感谢你看到这里，如果觉得本篇文章对你有帮助，点个赞👍 吧，你的点赞就是我更新的最大动力 ⛅️🌈 ☀️