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

r囧r小猫 2022-01-07 17:53 279阅读 0赞

### 文章目录 ###

*  顺序存储表示
 *  链式存储表示
 *   *  二叉链表
     *  三叉链表

# 顺序存储表示 #

以存储的数据是整型为例。

// 二叉树的最大节点数
    # define MAX_TREE_SIZE 100
    //0号单元存储根节点
    typedef int SqBiTree[MAX_TREE_SIZE];
    SqBiTree bt;

一棵二叉树的逻辑结构如下：

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

则其顺序存储结构如下：

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

由于二叉树不一定都是完全二叉树，所以希望通过标号来访问父节点以及兄弟、子节点的话，则必须为树添加虚节点。从上面的存储结构可以看出这样做的坏处就是会有大量的存储空间被浪费。

所以一般二叉树都用链式结构进行存储。

# 链式存储表示 #

## 二叉链表 ##

逻辑结构:

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

节点结构：

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

## 三叉链表 ##

逻辑结构：

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

节点结构：

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

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

若一个二叉树含有 n n n个结点，则它的二叉链表中必含有 2 n 2n 2n个指针域， 其中必有 n + 1 n +1 n\+1个空的链域。

证明：

分支数为 n − 1 n - 1 n−1，即非空的链域有 n − 1 n-1 n−1个，所以空的链域就等于 2 n − ( n − 1 ) = n + 1 2n - (n-1) = n + 1 2n−(n−1)=n\+1个。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70]: /images/20211220/a97ebba3e886473a8477ba16089ae50d.png
[20190630082327997.png]: /images/20211220/4df04633c06c4eb68bbc4b5695b8ca9e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 1]: /images/20211220/7c3b456aae1c4ac28bc0e1783c5ecbb7.png
[20190630082350911.png]: /images/20211220/8543196d6fe54099b97edd28c4e8f989.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2hqYzI1Ng_size_16_color_FFFFFF_t_70 2]: /images/20211220/82460cfdf34c4e97809d54472e2818ff.png
[20190630082419670.png]: /images/20211220/eb65070728024f4483a50e3b8d55d23d.png