学习数据结构--第四章:树与二叉树(二叉树的顺序存储和链式存储)

学习数据结构--第四章:树与二叉树(二叉树的顺序存储和链式存储)

Scroll Down

第四章:树与二叉树(二叉树的存储结构)

1.二叉树的顺序存储

二叉树的顺序存储

用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素。

思考为啥是存储完全二叉树?

这里正常情况存储的时数据,我们这里理解就存储编号了。但是如果使用上图存储,我们如何表示二叉树的逻辑关系呢?

二叉树的逻辑关系:1 是 2 和 3的双亲结点,2 3 是 1 的孩子结点。

这样的逻辑关机该如何维护呢?

我们在学习线性表的时候,我们知道线性表的地址是连续的,也就是线性表的下一个结点就是它下一个存储单元存放的元素,但是如果按照上图存储,一个节点的孩子结点一定是它接下来存放的元素吗?

二叉树逻辑关系的表示方法:

我们知道:在完全二叉树中依次编号,对于结点 i :若存在左孩子,则编号为 2i;若存在右孩子,则编号为 2i+1 。

所以我们使用这样的性质来实现二叉树逻辑关系。

在这里数组下标和结点的标号是一致的,这样我们就能使用下标来找到孩子结点下标了。这里为了更方便的对应完全二叉树性质,所以数组的第一个位置我们没有存储结点,当然其实也是可以存储的只不过找孩子结点的方式需要改变:左孩子 2i+1,右孩子2i+2 。其实我们在进行实际应用的是偶,0这个位置是会存储节点的个数的。

注意上面都是说的是完全二叉树


例如上图,是非完全二叉树,我们按照数组第一个位置空出来然后从上到下,从左到右,将结点依次填入数组,如上图。此时我们按如果按照上面的性质找3结点的左孩子为 2x3=6,按理说应该是存储在下标为6的地方,可以是实际上存储到下标为5的地方,这样就无法通过之前的方法来表示逻辑关系了。

那么该采用什么方法呢?

其实只需要对方法改进一下就行了。我们将这颗非完全二叉树 完全二叉树 ,即将 2 号结点补一个右孩子即可,然后进行存放。因为添加了一个不存在的空结点,所以在数组中用 0 表示

此时就表示了逻辑关系。虽然我们这样完成了二叉树的顺序存储的而且表示了逻辑关系,但是这样的存储方法是有一个 弊端 的。

如上图,我们如果将上面的二叉树使用顺序存储,则需要将其补成完全二叉树,这样我们就浪费了很多的存储空间来进行存放。所以:

顺序存储最坏情况会非常浪费存储空间,比较适合完全二叉树

因此我们在存储二叉树的时候往往使用链式存储。

2.二叉树的链式存储

二叉树的链式存储:用链表来存放一棵二叉树,二叉树中每个结点用链表的一个链结点来存储。

因为是二叉树,所以每个结点都可能有一个左孩子和右孩子,我们使用链表存放,所以可以每个结点可以定义一个数据域和两个指针域,两个指针域用来分别存储左结点和右结点。

我们举一个例子来看看具体是如何存放的。

因为某些结点没有左孩子或者右孩子,所以会出现空的指针域的情况,关于空指针域的个数我们有如下规律:

含有n个结点的二叉链表中,有 n+1 个空链域。

上面的结论是通过:2n-(n-1) 这个式子得到。式子的解释:

2n 表示每一个结点都有两个指针域,那么共n个结点,则总共 2n个指针域。我们要想的到空链域,则需要减去指针非空指针域。而非空指针域的个数其实就是孩子结点,有一个孩子结点,则需要一个指针域指向,而总共多少个孩子结点呢?总共为 n-1 个,因为 n 个结点中除了第一个结点是二叉树根节点外,其余都是孩子结点。故得到:2n-(n-1)=n+1

3.总结

本次学习了二叉树的顺序存储和链式存储,在实际应用中,对于顺序存储我们可能直接在数组的下标为1的位置开始存储二叉树,下标为0的位置存储二叉树的信息。

链式存储中,我们也可能需要三个指针域,除了指向左右孩子结点的指针域,还需要一个指向双亲结点的指针域。

关于数据结构的知识持续更新中,下次将会讲解:二叉树的遍历和线索二叉树,欢迎大家的关注,也可以关注同名公众号 理木客