(2)一般二叉树的顺序存储 存储方法:用完全二叉树的顺序存储方 法也可以存储一般二叉树。做法是:首先 在二叉树中补上着干虚拟结点使之成为一棵 完全二叉树;然后,按上述方法对结点进行 编号,并将它们存入数组rel1..m 中。其中m等于一般二叉树构成的虚拟完全 二叉树中的结点的个数。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 （２）一般二叉树的顺序存储 存储方法：用完全二叉树的顺序存储方 法也可以存储一般二叉树。做法是：首先， 在二叉树中补上若干虚拟结点使之成为一棵 完全二叉树；然后，按上述方法对结点进行 编号，并将它们存入数组tree[１．．m] 中。其中ｍ等于一般二叉树构成的虚拟完全 二叉树中的结点的个数
例如,图5-9给出了一棵一般二叉树的顺序存储结构。 R oO R ③③③③③③○③③③ 一般二叉树的逻辑结构补齐虚拟结点的完全二叉树的逻辑结构 1|23|45|67|8|9101112|131415 Tree AHIDGR 图5一9一般二叉树的顺序存储结构示意图
武汉理工大学华夏学院-信息工程 系 例如,图5－９给出了一棵一般二叉树的顺序存储结构。 一般二叉树的逻辑结构 A H D G R T S X Y A H D G R T S X Y 补齐虚拟结点的完全二叉树的逻辑结构 Tree １ 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Ａ H D G R T S X Y 图5－９一般二叉树的顺序存储结构示意图
存储特点: <心 占用的存储空间利用率较低,虛拟结点 在数组中要占用存储单元(不可能访问); 在确定各个结点之间的关系时,要进行判 断。如找图4-9中i=3的结点的左孩子 时,由其左孩子应放在下标为6的数组元 素单元中,但tre[6]为空,故可以断定 结点i无左子树。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 占用的存储空间利用率较低，虚拟结点 在数组中要占用存储单元（不可能访问）； 在确定各个结点之间的关系时，要进行判 断。如找图４－９中ｉ＝３的结点的左孩子 时，由于其左孩子应放在下标为６的数组元 素单元中，但 tree［６］为空，故可以断定 结点ｉ无左子树。 存储特点：
2、二叉树的二叉链表存储表示p心 存储方法:所谓二叉树的二叉链表存储表 示是指:对于树中的每一个结点用一个三元组 结构表示出来,其中包含有两个指针,分别指 向对应结点的左孩子结点的地址与右孩子结点 的地址。例如,图5-10给出了一棵一般二 叉树的二叉链表存储结构。 特点:利用动态变量存储树结构,并且各个结 点的孩子可以从结点本身反映出来 出时御防
武汉理工大学华夏学院-信息工程 系 特点：利用动态变量存储树结构，并且各个结 点的孩子可以从结点本身反映出来。 2、二叉树的二叉链表存储表示 存储方法：所谓二叉树的二叉链表存储表 示是指：对于树中的每一个结点用一个三元组 结构表示出来，其中包含有两个指针，分别指 向对应结点的左孩子结点的地址与右孩子结点 的地址。例如，图5－１０给出了一棵一般二 叉树的二叉链表存储结构。 这是一种常用的存储方法
般二叉树的逻辑结构「般二叉树的存储结构示意图 root H (R G R D 图5-10二又树的三叉链表存储结构示意图國心国 日心 系
武汉理工大学华夏学院-信息工程 系 一般二叉树的逻辑结构 A H D G R T S X Y root A ∧ H ∧ G ∧ R S ∧ X ∧ Y ∧ ∧ D ∧ ∧ T ∧ 一般二叉树的存储结构示意图 图5－10二叉树的二叉链表存储结构示意图