当前课程知识点：数据结构 > 第5章 树和二叉树 > 5.3 二叉树的存储 > 讲解
本节，我们来学习二叉树的存储
先来看顺序存储，顺序存储
就是用一维数组，依次存放二叉树当中每一个结点
我们可以采用刚才讲的完全二叉树的思想
对每一个结点进行编号
然后，用该编号作为结点
在一维数组当中的下标
比如，这样一棵二叉树
如果我们从上到下
从左到右，对结点进行编号
C这个结点
它的编号应该是3
那么，将来C在数组当中占的下标就是3
因为这样一棵二叉树
它正好是一棵完全二叉树
所以，我们发现，在一维数组当中
全部都存了元素
将来，我们根据
内存当中一维数组的元素
就可以直接还原回这个二叉树
比如，下标为1的
A
它肯定是整棵树的根，后面的B、C是A的左右孩子，紧接着的D和E是B的左右孩子，继续往后，按照完全二叉树
从上到下、从左到右这种编号方式，还原回二叉树就可以了
但是
如果我们要表达的二叉树
它不是一棵完全二叉树呢
比如这棵树
它并不是一棵完全二叉树
这时候，我们如果直接连续地存A、B、C、D
比如，这里是E、F，一直往后
将来还原回去，就会有问题
它并不能还原回这样一棵二叉树
为了防止还原的时候，出现歧义
我们必须将这棵不是完全二叉树的二叉树，给它补成一棵
完全二叉树
具体来说
就是把那些为空的结点
比如，我这里用#这个特殊的字符，来标识那些不存在的结点，B没有右孩子
必须要把它补上
包括这个不存在的右孩子
它的左右孩子，也要补上
因为，这棵二叉树有4层
必须把所有那些不存在的结点，都把它补上
让它变成一棵完全二叉树
这时候，我们才能存
比如，B的右孩子
是在D的兄弟的位置
D的下一位置
它必须要占一个存储单元
其他的不存在的孩子，也是类似的
只有让那些不存在的结点，也占据着数组的存储单元，我们才能够还原回去
很明显
顺序存储
只适合存储那些完全二叉树
非完全二叉树
需要补一些结点
可能会造成存储空间的浪费
在极端情况下
比如，树是这样的
一个仅仅包含5个结点的二叉树
我们要补的话
因为，它是高度为5的二叉树
补成完全二叉树
而且，E这个结点
它出现在树的最右下的位置
我们要补的话
必须一共要给它
补成包含31个结点的完全二叉树
这样，它的存储空间浪费就非常的严重
因为顺序存储会浪费空间
我们自然而然想到了第二种存储，也就是链式存储
链式存储
是按照有多少结点
就分配相应的内存来做的
具体来说
每个结点存放其左右孩子的指针
每个结点都带两个指针
所以，这时候的存放方式又称为二叉链表
具体来说
左边这样一棵二叉树
如果是画链表的结构
每一个结点都包含两个指针
分别是左孩子指针和右孩子指针
如果没有左孩子
相应位置的指针就是空
没有右孩子
相应位置的指针也是空
我们可以很容易地求出，具有n个结点的二叉链表
有n+1个空指针
这个很容易证明
因为，n个结点一共有2*n个指针
非空的指针有多少个呢
实际上
在图当中的这些边，就代表非空的指针
我们前面已经说过了，n个结点
它一共有n-1条边
所以，最后一共含有n+1个空指针
事实上
我们后面会想办法，把这n+1个空指针利用起来
让它们存一些有用的信息
方便我们对二叉树进行某些操作
我们来看具体的实现
如果我们定义结构体
3个成员，data表示结点自身的信息
比如，刚才的结点带的那些字母
A
B、C、D
left表示
该结点的左孩子指针，right表示该结点的右孩子指针
这样一个结构体
我们把它起名成
BinTreeNode，二叉树结点
我们也可以定义一个指向这个结点的指针
比如，BinTree，让它指向一个二叉树
包含3个结构体的结点
现在，我们来看具体的定义
首先
我们给树当中的结点起一个类型别名
ElemType
这里为了方便
我们认为，每一个结点就包含一个字符
char型，紧接着，定义一个结构体Node，第一个成员data
第二个和第三个成员，都是我们正在定义的
这个结构体
它的指针，left、right分别指向当前结点的左、右孩子
然后拿typedef，起两个别名
第一个别名，BinTreeNode，代表
整个这样一个结构体，也就是代表一个结点
第二个别名
是一个指针型别名，这个我们前面已经讲过了
用它声明的变量
即使不带*，也是一个指针
将来，如果我们用BinTree声明了一个变量
它指向一个结构体
我们为什么把这个别名定义成BinTree
二叉树呢
实际上，没有任何一个存储结构
能代表二叉链表在内存当中的整体结构
如果，我们拿一个指针指向二叉树
它的根结点
假设，这个指针是root，从根结点
我们根据左右孩子指针，就能找到根结点的孩子
然后，根据左右孩子，又能找到后面的结点
整个二叉树就唯一确定了
所以，只要知道
根结点的指针
就能够还原回二叉树
我们就把指向结点的指针别名
定义成
二叉树这样一种名称
-讲解
-作业
-讨论1
-讨论2
-1.1 数据结构是什么
--讲解
--作业
-1.2 概念和术语
--讲解
--作业1
--作业2
-1.3 抽象数据类型
--讲解（上）
--讲解（下）
--作业
-1.4 算法及其设计要求
--讲解
--作业
-1.5 算法分析与度量
--讲解（上）
--讲解（下）
--作业1
--作业2
--讨论
-2.1 概念及ADT
--讲解
--作业
-2.2 线性表的顺序实现——顺序表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.3 线性表的链式实现——链表
--讲解（上）
--讲解（中）
--讲解（下）
--作业1
--作业2
-2.4 线性表的应用——多项式
--讲解
--作业
-讨论
-3.1 栈的定义及ADT
--讲解
--作业
-3.2 栈的顺序实现——顺序栈
--讲解
--作业
-3.3 栈的应用
--讲解
--作业
-3.4 栈与递归
--讲解（上）
--讲解（下）
--作业
-3.5 队列的定义及ADT
--讲解
--作业
-3.6 队列的顺序实现——循环队列
--讲解（上）
--讲解（下）
--作业
-讨论
-4.1 数组的定义
--讲解
--作业
-4.2 数组的顺序实现
--讲解
--作业1
--作业2
-4.3 特殊矩阵的压缩存储
--讲解
--作业
-4.4 稀疏矩阵的压缩存储
--讲解（上）
--讲解（下）
--作业
-讨论
-5.1 概念及术语
--讲解
--作业
-5.2 二叉树及其性质
--讲解
--作业1
--作业2
-5.3 二叉树的存储
--讲解
--作业
-5.4 二叉树的遍历及创建
--讲解（上）
--讲解（下）
--作业
-5.5 线索二叉树
--讲解
--作业
-5.6 树与森林
--讲解
--作业
-5.7 Huffman树
--讲解（上）
--讲解（下）
--作业
-讨论
-6.1 概念和术语
--讲解
--作业
-6.2 存储与实现
--讲解（上）
--讲解（下）
--作业
-6.3 遍历
--讲解（上）
--讲解（下）
--作业
-6.4 最小生成树
--讲解（上）
--讲解（下）
--作业1
--作业2
-6.5 拓扑排序
--讲解
--作业
-6.6 最短路径
--讲解
--作业
-讨论
-7.1 概念和术语
--讲解
--作业
-7.2 静态查找表
--讲解（上）
--讲解（下）
--作业
-7.3 二叉排序树
--讲解（上）
--讲解（下）
--作业
-7.4 平衡二叉树
--讲解
--作业
-7.5 哈希表
--讲解（上）
--讲解（下）
--作业
-讨论
-8.1 概念
--讲解
--作业
-8.2 插入排序
--讲解（上）
--讲解（下）
--作业
-8.3 交换排序
--讲解（上）
--讲解（下）
--作业
-8.4 选择排序
--讲解（上）
--讲解（中）
--讲解（下）
--作业
-8.5 归并排序
--讲解
--作业
-讨论
