🎬 鸽芷咕:个人主页 🔥 个人专栏:《速学数据结构》 《C语言进阶篇》
⛺️生活的理想,就是为了理想的生活!
🌈hello! 各位宝子们大家好啊,关于线性表我们已经在前面更新完了! ⛳️今天就来看一下复杂一些的数据结构 “树” 他的应用主要在哪些方面呢?以及结构是什么样的 📚本期文章收录在《数据结构&算法》,大家有兴趣可以看看呐! ⛺️ 欢迎铁汁们 ✔️ 点赞 👍 收藏 ⭐留言 📝!
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
可能大家还不是很了解但大家看上面这张图,左边是一棵树,右边就是我们的 多叉树数据结构了;
注意:树形结构中,子树之间不能有交集,否则就不是树形结构
前面我们说了树是由 一个根节点加很多 子孙节点 组成的,那么他们相应的叫法是什么呢?
其中红色标记的是比较重要的概念大家可以重点记一下这些都是选择题经常出现的概念,像树的深度树的层级
等等这样的题如果不了解这些概念的话是根本做不了的
诶不知道大家注意过没有我们的文件夹和树的结构很类似?
这里 Linux 的文件目录就是用多叉树实现的。
树的概念我们讲解了,但是其实我们应用最广的还是二叉树比如 八大排序里面的 堆排序 和 快速排序 全都应用了树的思想。
那么什么是二叉树呢? 其实二叉树就是结点的一个有限集合
一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是
,则它就是 满二叉树。
完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
二叉树是什么我们前面了解过了那么二叉树有那些性质是需要我们来了解一下的呢?
个结点.
.
, 度为2的分支结点个数为
,则有
=
+1
. (ps:
是log以2为底,n+1为对数)
好了讲了这么多大家估计也听的很迷糊,不要慌接下来我们就来看一下二叉树的实现来带大家吃下肉:
🔥 注:一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费
大家看这个图片一但使用数组来存储普通的二叉树就会造成很大的空间浪费,顺序存储是由数组进行控制的。
📚 代码演示:
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a; //存储数据的数组
int size; //存储的数据个数
int capacity; //二叉树的容量
}HP;
二叉树的链式结构就很简单了,我们前面说了利用顺序存储会造成空间的浪费而链式存储的就避免了这种情况和链表一样。
🔥 注意:上述代码并不是创建二叉树的方式,只是给大家演示一下后面博主会出一篇博文来进行讲解的。 📚 代码演示:
typedef int BTDataType;
typedef struct BinaryTreeNode
{
BTDataType _data;
struct BinaryTreeNode* _left;
struct BinaryTreeNode* _right;
}BTNode;
BTNode* CreatBinaryTree()
{
BTNode* node1 = BuyNode(1);
BTNode* node2 = BuyNode(2);
BTNode* node3 = BuyNode(3);
BTNode* node4 = BuyNode(4);
BTNode* node5 = BuyNode(5);
BTNode* node6 = BuyNode(6);
node1->_left = node2;
node1->_right = node4;
node2->_left = node3;
node4->_left = node5;
node4->_right = node6;
return node1;
}