数据结构之树-二叉树的存储结构-学习笔记-53

引入

前面，我们学习了二叉树的五大特性，那么既然说了这么久的二叉树，是时候讲一讲二叉树的数据结构该如何定义了。

回顾

如果你忘了之前的内容，点击下面的链接回顾：
数据结构之树-树的存储结构（一）-学习笔记-47
数据结构之树-树的存储结构（二）-学习笔记-47

思考

根据我们之前讨论树的存储结构，我们可以直到，树和结点里面包含的元素可以很灵活，我们甚至可以将链式存储结构跟顺序存储结构结合在一起使用。因为这样表达树这个数据结构才方便。但是

• 二叉树是一种特殊的树，由于它的特殊性，使得
• 顺序存储结构和链式存储结构都可以轻松的实现二叉树

二叉树的顺序存储结构

二叉树的顺序存储结构就是利用一维数组

• 数组中存放二叉树的各个结点
• 各个结点的存储位置能体现结点之间的逻辑关系

上面的图中是一棵完全二叉树，我们将它存放进一维数组

元素	A	B	C	D	E	F	G
下标	1	2	3	4	5	6	7

我们发现，使用层序法排列的完全二叉树

• 元素是 ABCDEFG
• 下标是 1234567
• 完美！（下标0存储的是结点个数）
• 我们完全可以通过上面的一维数组，使用层序法，重新画出这课二叉树。

我们在看一下这张图，图中并不是完全二叉树，更不是满二叉树

• 如果遇到空结点，我们使用^，代替即可

元素	A	B	C	D	^	F	G
下标	1	2	3	4	5	6	7

还记得斜二叉树嘛？

它的存储可能会是

元素	A	B	^	C	^	^	^
下标	1	2	3	4	5	6	7

这里我们就发现不对了！

• 数组长度有8个
• 因为是斜树，浪费了一半多的存储空间
• 所以，顺序存储结构之后，链式存储应运而生。

二叉树的链式存储结构

在说明链式存储结构前，我们先想象，如果是链式结构

• 一个存数据，两个存左子树和右子树最棒了
• 我们称这样的链表，叫做二叉链表。

左子树指针域	数据域	右子树指针域
Lchild	Data	Rchild

struct BTNode{
int data;  //存放数据
struct BTNode *Lchild;  //存放左子树结点位置
struct BTNode *Rchild;  //存放右子树结点位置
};

如图所示，我们就可以使用链表构建一棵树了，非常简单！
我们之后基本上都是用链式存储结构构建二叉树。

尾巴

这是我的个人学习笔记，主要是应付考研复习使用，充斥着一些吐槽和个人观点，并不严谨，欢迎大家参考、指正。