数据结构 第07章 树和二叉树2.pdf

7.2.4 二叉树的存储结构 二叉树的存储结构解决的主要问题是什么？ 二叉树的存储结构既要存储各结点的信息，还要 反映二叉树的逻辑关系，即双亲关系和孩子关系，并 方便子向父或父向子的访问。 三种存储结构： 1、顺序存储 2、链式存储 3、仿真指针 1 二叉树的顺序存储结构 顺序结构中的一对一与树型结构中的一对多的矛盾。 顺序结构只能用来存储特殊的二叉树：完全二叉树。 完全二叉树中层序号的性质？ ? i  由于任意一个结点 i 的父结点、左右子结点的 序号都可以根据公式计算得出 因此，完全二叉树的结点可按照从上至下、从 左至右的顺序存储在一维数组中，其结点之间 的 关系可根据公式计算得到 这就是二叉树的顺序存储结构 A B C A B C D E F G H I J D E F G 0 1 2 3 4 5 6 7 8 9 H I J ① 如果i=0，则结点i是根结点，无双亲。 如果i0，则其父结点的序号：(i-1)/2 (“/” ② 如果2i+1＜n ，其左子结点的序号：2i+1； 如果2i+1≥n，则结点 i无左结点。 ③ 如果2i＋2＜n，其右子结点的序号：2i＋2； 如果2i＋2≥n，则结点 i无右子结点。 对于一般的非完全二叉树显然不能直接使用二叉树 的顺序存储结构。可以首先在非完全二叉树中增添一些 并不存在的空结点使之变成完全二叉树的形态，然后再 用顺序存储结构存储。 A A B C B C D E D E G F G F (a)一般二叉树 (b)完全二叉树形态 (c) 在数组中的存储形式 2、二叉树的链式存储结构 ① 二叉树的链式存储结构是用指针建立二叉 树中结点之间的关系。 ②二叉树最常用的的链式存储结构是二叉链 ③二叉链存储结构的每个结点包含三个域， 分别是数据域data、左孩子指针域leftChild 和右孩子指针域rightChild 。 ④二叉链存储结构中每个结点的图示结构为 二叉链存储结构的二叉树也有不带头结点和带头 结点两种。 不带头结点的二叉链存储结构的二叉树如图(a) 带头结点的二叉链存储结构的二叉树见下图(b) (a)不带头结点的二叉树 (b)带头结点的二叉树 7.3 以结点类为基础的二叉树设计 二叉树的实现有两种基本方法： ① 首先设计二叉树结点类，然后在二叉树结点类的基 础上，用结点类的外部函数实现二叉树的操作； ② 在二叉树结点类的基础上，再设计二叉树类。 1.二叉树的结点类 模板形式的二叉树结点类定义和实现代码如下： template class T class BiTreeNode { private: BiTreeNodeT *l