83二叉树的设计和实现 831二叉树的存储结构 二叉树的存储结构主要有三种:顺序存储结构、链式存储结 构和仿真指针存储结构 1.二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在 维数组中,其结点之间的关系可由公式计算得到,这就是二 叉树的顺序存储结构。下面两棵树在数组中的存储结构分别 为
8.3.1二叉树的存储结构 二叉树的存储结构主要有三种：顺序存储结构、链式存储结 构和仿真指针存储结构。 1. 二叉树的顺序存储结构 完全二叉树的结点可按从上至下和从左至右的次序存储在一 维数组中，其结点之间的关系可由公式计算得到，这就是二 叉树的顺序存储结构。下面两棵树在数组中的存储结构分别 为： 8.3二叉树的设计和实现
E 0000060 ABCDEFGHIJKLMNO 01234567891011121314
B A C D E F G H I J K L M N O A B C D E F G H I J K L M N O 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
000 ABCDEFGHIJ 0123456789 对于一般的非完全二叉树显然不能直接使用二叉树的顺序存 储结构。可以首先在非完全二叉树中增添一些并不存在的空结点 使之变成完全二叉树的形态,然后再用顺序存储结构存储
对于一般的非完全二叉树显然不能直接使用二叉树的顺序存 储结构。可以首先在非完全二叉树中增添一些并不存在的空结点 使之变成完全二叉树的形态，然后再用顺序存储结构存储。 B A C D E F G H I J A B C D E F G H I J 0 1 2 3 4 5 6 7 8 9
D (a)一般二叉树 (b完全二叉树形态 数组ABC∧DE∧∧∧F∧∧G 下标0123456789101112 (c)在数组中的存储飛式
B A C D E F G B A C D E F G (a)一般二叉树 (b)完全二叉树形态 (c) 在数组中的存储形式 A B C ∧ D E ∧ ∧ ∧ F ∧ ∧ G 0 1 2 3 4 5 6 7 8 9 10 11 12 数组 下标
2.二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。 叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每 个结点包含三个城,分别是数据城data、左孩子指针域 leftchild 和右孩孑指针域 Right child。二叉链存储结构中每个结点的图示 结构为: left Child data right child 二叉链存储结构的二叉树也有不带头结点和带头结点两种。 带头结点的二叉链存储结构的二叉树见下图(b),不带头结点的 二叉链存储结构的二叉树如下图(a)所示
2. 二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。 二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每 个结点包含三个域，分别是数据域data、左孩子指针域leftChild 和右孩子指针域rightChild。二叉链存储结构中每个结点的图示 结构为： leftChild data rightChild 二叉链存储结构的二叉树也有不带头结点和带头结点两种。 带头结点的二叉链存储结构的二叉树见下图(b)，不带头结点的 二叉链存储结构的二叉树如下图(a)所示