数据结构(9) 树[三]（二叉树存储结构）

男娘i 2022-02-03 06:55 260阅读 0赞

# 数据结构——二叉树的存储结构 #

之前已经谈过了树的存储结构，并且说到顺序存储对树这一种一对多的关系的结构实现起来比较困难。但是二叉树是一种特殊的树，由于它的特殊性，使得用**顺序存储结构**也可以实现。

# 二叉树的顺序存储结构 #

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标，要能体现结点之间的逻辑关系，如双亲与孩子的关系，左右兄弟的关系等。

先来看完全二叉树的顺序存储，一棵完全二叉树如图所示：

![img][]

将这颗二叉树存入到数组中，相应的下表对应其同样的位置，如图：

![img][img 1]

**由于二叉树严格的定义，所以用顺序存储结构也可以表现出二叉树的结构来。**

当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的结点设置为^就可以。下图浅色部分表示不存在：

![img][img 2]

考虑一种极端的情况，一棵深度为k的右斜树，他只有k个结点，却需要分配2的k次-1个存储单元，造成明显的浪费，如图，所以顺序存储结构一般只用于完全二叉树：

![img][img 3]

# 二叉链表 #

既然顺序存储适用性不强，就要考虑链式存储结构。

**二叉树最多有两个孩子，所以为他设计一个数据域和两个指针域是最合适不过的，我们把这样的链表叫做二叉链表。**

结构图如下：

![img][img 4]

其中data是数据域，lchild和rchild都是指针域，分别存放指向左孩子和右孩子的指针。

![img][img 5]

[img]: /images/20220203/58ba631e34f344fa9071fd002ca38cdd.png
[img 1]: /images/20220203/547308245d8a4178ab734cca339af300.png
[img 2]: /images/20220203/68640e7a6e664cf393172fb59bf26b27.png
[img 3]: /images/20220203/e94c6b2a2b6243bd9e47dd7211215904.png
[img 4]: /images/20220203/1c878f5ae611486a9d85e2cdef6c2fa2.png
[img 5]: /images/20220203/ec066820056a4b5b804bbb50683ec545.png

发表评论取消回复

表情：

评论列表（有 0 条评论，260人围观）

还没有评论，来说两句吧...

相关阅读

相关数据结构-顺序存储二叉树

文章目录目录文章目录前言一 . 什么是顺序存储二叉树二 . 模拟实现前序遍历总结 -------------------- 前言 >

爱被打了一巴掌/ 2024年03月01日 07:45/ 0 赞/ 75 阅读

相关数据结构-树、二叉树

一、概念 1、树的概念 ![a2c54e1c3956460cb4b78e8a78646577.png][] 树是一种非线性的数据结构，它是由n(n>=0)个有限结

快来打我*/ 2023年10月13日 10:04/ 0 赞/ 92 阅读

相关数据结构_顺序存储二叉树

文章目录基本说明特点代码实现基本说明从数据存储来看，数组存储方式和树的存储方式可以相互转换。特点

客官°小女子只卖身不卖艺/ 2023年07月11日 06:17/ 0 赞/ 27 阅读

相关【数据结构】图解二叉树的存储结构

文章目录二叉树的顺序存储结构二叉链表二叉树的顺序存储结构二叉树的存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也

迷南。/ 2023年02月19日 11:24/ 0 赞/ 124 阅读

相关 9.数据结构之二叉树

数据结构之二叉树 -------------------- 树的简介之前我们接触了一维线性数据结构双端链表、动态数组以及他们的变形结构栈和队列，以及它们的组合结

亦凉/ 2022年08月20日 06:25/ 0 赞/ 29 阅读

相关二叉树的存储结构（数据结构）

1. 链式存储结构即单链表结构或双链表结构（同树）。数据结构修改如下： typedef struct node; type

港控/mmm°/ 2022年06月09日 06:48/ 0 赞/ 256 阅读

相关数据结构——树—— 二叉树及存储结构

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查

电玩女神/ 2022年04月16日 04:06/ 0 赞/ 285 阅读

相关数据结构(9) 树[三]（二叉树存储结构）

数据结构——二叉树的存储结构之前已经谈过了树的存储结构，并且说到顺序存储对树这一种一对多的关系的结构实现起来比较困难。但是二叉树是一种特殊的树，由于它的特殊性，使得用顺

男娘i/ 2022年02月03日 06:55/ 0 赞/ 261 阅读

相关数据结构--二叉树的存储结构

文章目录顺序存储表示链式存储表示二叉链表三叉链表顺序存储表示以存储的数据是整型为例。 // 二叉树的最

r囧r小猫/ 2022年01月07日 17:53/ 0 赞/ 363 阅读

相关【数据结构】二叉树顺序存储结构实现

二叉树顺序结构的存储实现是用数组存储的，使用下标存储第i个节点。二叉树的顺序存储结构非常适合存储满二叉树，这使得二叉树的存储占用最少。在数组中完全二叉树中没有双亲节点的值用

r囧r小猫/ 2021年09月21日 08:18/ 0 赞/ 470 阅读