二叉树的存储结构（数据结构学习笔记）

缺乏、安全感 2022-12-28 04:22 287阅读 0赞

### 文章目录 ###

*   *  顺序存储结构
     *   *  完全二叉树的顺序存储结构
         *  非完全二叉树的顺序存储结构
         *  顺序存储结构的类型声明
         *  优缺点
     *  二叉树的链式存储结构
     *   *  优缺点
         *  改进
         *  空指针个数

--------------------

主要介绍二叉树的顺序存储结构和链式存储结构

## 顺序存储结构 ##

顺序存储结构主要`利用二叉树的性质4，将完全二叉树结点按照层次编号：`

如图所示：

![在这里插入图片描述][20201214170109205.png]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

### 非完全二叉树的顺序存储结构 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]

### 顺序存储结构的类型声明 ###

（我们认为空结点用 \# 表示）

typedef ElemType SqBinTree[MaxSize];

### 优缺点 ###

*  顺序存储结构存放二叉树，**对于完全二叉树而言非常合适**
 *  **当对于具有很多单分支结点的二叉树而言不合适，特别是退化的二叉树，空间浪费很大**
 *  用顺序存储结构存放二叉树，**很容易就可以找到一个结点的双亲和孩子**

## 二叉树的链式存储结构 ##

这里**借鉴树的孩子链存储结构**来类比二叉树的链式存储结构

如图所示：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]

\#\#\#　结点类型定义：

typedef struct node
    {
        
        ElemType data;
        struct node *lchild;
        struct node *rchild;
    }BTNode;

### 优缺点 ###

*  除了指针外，二叉链**比较节省存储空间**。占用的存储空间与树形没有关系，**只与树中结点个数有关**。
 *  在二叉链中，**找一个结点的孩子很容易**，**但找其双亲不方便**。

### 改进 ###

*  有时候可以**再加一个指向双亲的指针域parent**，就可以高效地访问一个结点的双亲结点。

如图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]

### 空指针个数 ###

在二叉链中

*  树有 n 个结点，每个结点都有左右孩子，则有 2n 个指针域
 *  分支数为 n-1 个，即非空指针域有 n-1 个
 *  那么空指针域个数 = 2n-(n-1) = n+1 个

如图所示：

![在这里插入图片描述][20201214170136182.png]

*  学习数据结构教程（第五版）——李春葆教授主编
 *  图片来源于MOOC，数据结构——武汉大学——李春葆教授
 *  （如若侵权可联系QQ删除）

[20201214170109205.png]: /images/20221120/c8072aff2ee74350827c4c4549f8ad45.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/c44ba7e0ff9b49d6a46ef8c928de52ce.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20201214170120989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20201214170126268.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20201214170131166.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng==,size_16,color_FFFFFF,t_70
[20201214170136182.png]: https://img-blog.csdnimg.cn/20201214170136182.png