下面给出一棵完全二叉树的顺序存储示意。 5(F)6 一棵完全二叉树 BCDEFGHI 数组下标 完全二叉树的顺序存储示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 16 •下面给出一棵完全二叉树的顺序存储示意
·对于一般的二叉树,如果仍按从上至下和从左到右的顺 序将树中的结点顺序存储在一维数组中,则数组元素下标 之间的关系不能够反映二叉树中结点之间的逻辑关系,只 有增添一些并不存在的空结点,使之成为一棵完全二叉树 的形式,然后再用一维数组顺序存储。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 17 • 对于一般的二叉树，如果仍按从上至下和从左到右的顺 序将树中的结点顺序存储在一维数组中，则数组元素下标 之间的关系不能够反映二叉树中结点之间的逻辑关系，只 有增添一些并不存在的空结点，使之成为一棵完全二叉树 的形式，然后再用一维数组顺序存储
如图给出了一棵一般二叉树改造后的完全二叉树形态 和其顺序存储状态示意图。显然,这种存储对于需增加 许多空结点才能将一棵二叉树改造成为一棵完全二叉树 的存储时,会造成空间的大量浪费,不宜用顺序存储结 构 (a)一棵二叉树 b)改造后的完全二叉树 ABCADIEAAAFAAG (c)改造后完全二叉树顺序存储状态 般二叉树及其质序存储示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 18 • 如图给出了一棵一般二叉树改造后的完全二叉树形态 和其顺序存储状态示意图。显然，这种存储对于需增加 许多空结点才能将一棵二叉树改造成为一棵完全二叉树 的存储时，会造成空间的大量浪费，不宜用顺序存储结 构
最坯的情况是右单支树,一棵深度为k的右单支树,只 有k个结点,却需分配2k-1个存储单元。 ●●●c 00000o (a)一棵右单支二叉树 b)改造后的右单支树对应的完全二叉树 ∧BA∧∧cAAA∧∧∧ (c)单支树改造后完全二叉树的顺序存储状态 右单支二叉树及其顺序存储示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 19 • 最坏的情况是右单支树，一棵深度为k的右单支树，只 有k个结点，却需分配2 k－1个存储单元
2.链式存储结构 (1)二叉链表存储 」链表中每个结点由三个域组成,除了数据域外,还有 两个指针域,分别用来给出该结点左孩子和右孩子所在 的链结点的存储地址。结点的存储的结构为: Child data rchild 其中,data或仔放某结点的数据; lchild rchild分别存放指向左孩子和右孩子的指针,当左孩子 或右孩子不存在时,相应指针域值为空(用符号∧或 NUL表示) 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 20 2．链式存储结构 （1）二叉链表存储 链表中每个结点由三个域组成，除了数据域外，还有 两个指针域，分别用来给出该结点左孩子和右孩子所在 的链结点的存储地址。结点的存储的结构为： 其中，data域存放某结点的数据信息；lchild 与 rchild分别存放指向左孩子和右孩子的指针，当左孩子 或右孩子不存在时，相应指针域值为空（用符号∧或 NULL表示）