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

迷南。 2023-02-19 11:24 65阅读 0赞

### 文章目录 ###

*   *  二叉树的顺序存储结构
     *  二叉链表

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

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

首先看一下完全二叉树的顺序存储，一颗完全二叉树如图1-1所示。  
![在这里插入图片描述][20200620131543851.png_pic_center]

图1-1  
将这颗二叉树存入到数组中，相应的下标对应其同样的位置，如图1-2所示。  
![在这里插入图片描述][20200620131733651.png_pic_center] 图1-2  
这下看出完全二叉树的优越性了吧。由于它定义的严格，所以用顺序结构也可以表现出二叉树的结构来。  
当然对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把存在的结点设置为“^”而已。如图1-3中，注意浅色结点表示不存在。  
![在这里插入图片描述][20200620132130300.png_pic_center] 图1-3  
考虑一种极端的情况，一颗深度为k的右斜树，他只有k个结点，却需要分配2 k\-1个存储单元，这显然是对存储空间的浪费，例如图1-5所示，所以顺序存储结构一般只用于完全二叉树。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70] 图1-5

## 二叉链表 ##

既然顺序存储的适用性不强，我们就要考虑链式存储结构。\*\*二叉树每个结点最多有两个孩子，所以为他设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表，\*\*结构如图1-6所示。  
![在这里插入图片描述][202006201328535.png_pic_center]

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

//二叉树的二叉链表结点结构定义
    typedef struct BiNode
    {
        
    	TElemType data;    				//结点数据
    	struct BiTNode *lchild,*rchild;  //左右孩子指针
    }

结构示意图如图1-7所示。  
![在这里插入图片描述][20200620133242906.png_pic_center]

图1-7

[20200620131543851.png_pic_center]: https://img-blog.csdnimg.cn/20200620131543851.png#pic_center
[20200620131733651.png_pic_center]: https://img-blog.csdnimg.cn/20200620131733651.png#pic_center
[20200620132130300.png_pic_center]: https://img-blog.csdnimg.cn/20200620132130300.png#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200620132424906.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3hpYW5nanVueWVz,size_16,color_FFFFFF,t_70
[202006201328535.png_pic_center]: https://img-blog.csdnimg.cn/202006201328535.png#pic_center
[20200620133242906.png_pic_center]: https://img-blog.csdnimg.cn/20200620133242906.png#pic_center