二叉树的存储结构

📙作者简介： 清水加冰，目前大二在读，正在学习C/C++、Python、操作系统、数据库等。

📘相关专栏：C语言初阶、C语言进阶、C语言刷题训练营、数据结构刷题训练营、有感兴趣的可以看一看。

欢迎点赞 👍 收藏 ⭐留言 📝 如有错误还望各路大佬指正！

✨每一次努力都是一种收获，每一次坚持都是一种成长✨       

目录

 前言

1. 二叉树的存储结构

1.1 链式存储结构

1.2 二叉树的顺序存储

1.2.1 树的双亲表示法

1.2.2 堆

 2. 拓展

总结

---

 

 前言

        二叉树的存储结构是指如何将二叉树的节点和它们之间的关系表示出来，以便于对二叉树进行操作和遍历。在二叉树的存储结构中，我们有多种选择，每种选择都有其独特的优势和适用场景。从链式存储到顺序存储，再到堆存储，每种方法都有不同的空间和时间复杂度，并且适用于不同的应用场景。

---

1. 二叉树的存储结构

        二叉树的存储结构可以分为两大类：

一、顺序结构存储

二、链式结构存储

1.1 链式存储结构

        二叉树的链式存储结构，顾名思义就是使用链表来表示二叉树，使用链表来表示二叉树的结构，通常是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。如下图：

 二叉链的定义：

struct BinaryTreeNode
{
struct BinTreeNode* pLeft; // 指向当前节点左孩子
struct BinTreeNode* pRight; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}；

        链式结构又分为二叉链和三叉链，当前我们学习中一般都是二叉链，后面学到高阶数据结构如红黑树等会用到三叉链。如下图：

 三叉链的定义：

struct BinaryTreeNode
{
struct BinTreeNode* pParent; // 指向当前节点的双亲
struct BinTreeNode* pLeft; // 指向当前节点左孩子
struct BinTreeNode* pRight; // 指向当前节点右孩子
BTDataType data; // 当前节点值域
}；

1.2 二叉树的顺序存储

         二叉树的顺序存储对二叉树是有一定要求的，普通的二叉树不适合使用顺序存储，会造成空间上的浪费。如下图：

        只要完全二叉树才可以使用顺序存储

如下图： 

 那么数组存储的原理或者说逻辑是什么？

1.2.1 树的双亲表示法

 使用顺序存储的表示方法有多种，如双亲表示法：孩子节点只存储双亲的下标 如下图：

         A没有父亲所以存储的是-1，B和C的父亲是A，A的下标是0，所以B、C存储的都是A的数组下标。D、E的父亲是B，所以D、E存储的B的下标即1……

        我们也可以通过这样的方法来判断有多少棵树，在后续的学习中我们还会遇到森林，森林就是有多颗树组成的结构，如果节点为树的根就存储-1，我们可以计算-1的个数就可以判断树的数量。

1.2.2 堆

        说到二叉树的顺序存储，这里就要引入一个新的概念——堆。堆又可以分为2种：

大堆：大堆的子节点不得大于父节点。

小堆：小堆的子节点不得小于父节点。

 大堆：

小堆：

         通过观察我们可以发现数组在存储二叉树的节点时是按照从左到右，逐层存储的，所以，在给出的任意一个数组，都可能组成一个二叉树（逻辑上），从数组如何变换到二叉树的树形结构呢？其实也很简单。数组的首元素必定是二叉树的根，然后根据完全二叉树的特性进行逐层分割。

以上图的小堆为例：

10可以作为一个二叉树的根:

        那我们在写代码的时候要如何去判断根节点的子节点呢？前辈们已经总结出了规律：

leftChild=parent*2+1;
rightChild=parent*2+2;
 
parent=(Child-1)/2;//或者 parent=(Child-2)/2

        任何一个节点都可以下标找到它的父节点。看到堆的顺序存储，我们也会很容易联想到栈的顺序存储。我们可以来对比一下：

栈：是一种线性表，具有先进后出的特性。

堆：是非线性结构，只能是完全二叉树。

 2. 拓展

 堆的底层：

堆在物理层面，正如我们所看到的顺序存储，是数组。

在逻辑层面，它是一颗完全二叉树。

那么问题来了，堆一定是有序的吗？

        根据上边的两个例子，答案已将显而易见了，不一定。堆的头一定是整个数组中的最值（最大或最小） 。既然堆是数组，那我们也是可以对堆进行排序的，这里旧会引入后续会学习的——堆排序。

 那么堆排序它有什么价值呢？

        我们知道冒泡排序的时间复杂度是O(N^2)，而堆排序的时间复杂度是O(NlogN)，它们的效率可是天差地别，例如我们以100W个数为例，冒泡要执行1万亿次，而堆排序只需要2000万次，它们相差多少次。

 其次就是topk问题，什么是topk问题？

topk问题就是找出最大或最小的前k个。拓展部分目前仅为了解内容，后续都会进行介绍。

---

总结

        通过本篇博客，我们深入探讨了二叉树的存储结构，包括链式存储、顺序存储、堆存储。每种存储方式都有其独特的优点和适用场景，希望本篇博客能够为读者提供有价值的知识和见解，帮助大家更好地理解和应用二叉树的存储结构。让我们一起在二叉树的世界中探索，发现更多的可能性！