讲解在线视频

本节，我们来学习二叉树的存储

先来看顺序存储，顺序存储

就是用一维数组，依次存放二叉树当中每一个结点

我们可以采用刚才讲的完全二叉树的思想

对每一个结点进行编号

然后，用该编号作为结点

在一维数组当中的下标

比如，这样一棵二叉树

如果我们从上到下

从左到右，对结点进行编号

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，从根结点

我们根据左右孩子指针，就能找到根结点的孩子

然后，根据左右孩子，又能找到后面的结点

整个二叉树就唯一确定了

所以，只要知道

根结点的指针

就能够还原回二叉树

我们就把指向结点的指针别名

定义成

二叉树这样一种名称