admin管理员组

文章数量:1794759

【数据结构】你知道什么是二叉树的顺序存储结构吗？

前言

二叉树一般可以使用两种结构存储，一种顺序结构，一种链式结构。本文将要介绍的是二叉树的顺序存储结构。

1. 顺序结构

顺序结构存储就是使用数组来存储，一般使用数组只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费，完全二叉树更适合使用顺序结构存储。

现实中我们通常把堆（一种二叉树）使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

2. 实现顺序结构二叉树

一般堆使用顺序结构的数组来存储数据，堆是一种特殊的二叉树，具有二叉树的特性的同时，还具备其他的特性。

2.1 堆的概念与结构

如果有一个关键码的集合 K = { k 0 , k 1 , k 2 , . . . , k n − 1 } K = \{{k_0,k_1,k_2 , ...,k_{n−1}}\} K={k0​,k1​,k2​,...,kn−1​}，把它的所有元素按完全二叉树的顺序存储方式存储，在一个一维数组中，并满足： K i < = K 2 ∗ i + 1 且 K i < = K 2 ∗ i + 2 ( K i > = K 2 ∗ i + 1 且 K i > = K 2 ∗ i + 2 ) K_i <= K_{2*i+1} 且K_i <=K_{2*i+2}(K_i >=K_{2*i+1}且K_i >= K_{2*i+2}) Ki​<=K2∗i+1​且Ki​<=K2∗i+2​(Ki​>=K2∗i+1​且Ki​>=K2∗i+2​)，

堆具有以下性质：

  • 堆中某个结点的值总是不大于或不小于其父结点的值；
  • 堆总是一棵完全二叉树。

本文标签： 数据结构你知道什么是二叉树的顺序存储结构吗

版权声明：本文标题：【数据结构】你知道什么是二叉树的顺序存储结构吗？ 内容由林淑君副主任自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.xiehuijuan.com/baike/1754680745a1705120.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。