引入
前面,我们学习了二叉树的五大特性,那么既然说了这么久的二叉树,是时候讲一讲二叉树的数据结构该如何定义了。
回顾
如果你忘了之前的内容,点击下面的链接回顾:
数据结构之树-树的存储结构(一)-学习笔记-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 |
1 | struct BTNode{ |
如图所示,我们就可以使用链表构建一棵树了,非常简单!
我们之后基本上都是用链式存储结构构建二叉树。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。