思考:如何设法将顺序存储方法扩 展应用于一棵非完全二叉树? 添加⑥ 结点 000 ABC D F G H 1234567891011121314
计 算 机 软 件 基 础 思考：如何设法将顺序存储方法扩 展应用于一棵非完全二叉树？ A B C D E F G H A B C D E F G H A B C D E F G H 1 2 3 4 5 6 7 8 9 10 11 12 13 14 添加虚 结点
令分析以上采用的存储方法的利弊。 结论 虽然通过添加虚结点的办法可将一棵普 通二叉树构造成一棵完全二叉树并对其进行 顺序存储,但这种做法既繁琐,又造成了大 量存储空间的浪费,故该方法在实际工作中 很少被使用
计 算 机 软 件 基 础 ❖ 分析以上采用的存储方法的利弊。 结论： 虽然通过添加虚结点的办法可将一棵普 通二叉树构造成一棵完全二叉树并对其进行 顺序存储，但这种做法既繁琐，又造成了大 量存储空间的浪费，故该方法在实际工作中 很少被使用。
(2)链式存储结构 实现方法:二叉树的链式存储结构中最常用 的是二叉链表,其结点结构包括三个域,其 中一个是数据域,用于存放结点的数据值; 另外两个是指针域,分别存放该结点的左孩 子和右孩子的地址。除此之外,为了存储根 结点的地址,还需设立一个指针变量tree Child data rchild
lchild data rchild 计 算 机 软 件 基 础 （2）链式存储结构 实现方法：二叉树的链式存储结构中最常用 的是二叉链表，其结点结构包括三个域，其 中一个是数据域，用于存放结点的数据值； 另外两个是指针域，分别存放该结点的左孩 子和右孩子的地址。除此之外，为了存储根 结点的地址，还需设立一个指针变量tree。
例:对如下二叉树采用二叉链表方式进行 链式存储 tree A B B∧ C F ∧D E闪DF人 H 二叉树示意图 链式存储示意图
计 算 机 软 件 基 础 F ∧ ∧ A B C ∧ D ∧ E ∧ tree ∧ G ∧ ∧ H ∧ A B C D E F G H 例：对如下二叉树采用二叉链表方式进行 链式存储。 二叉树示意图 链式存储示意图
二叉链表中结点类型的定义: typedef struct node i datatype data; struct node x lchild s rchild )bstree; Child data rchild 注意: datatype在此处代表任意数据类型,实现时应根 据结点的实际数据类型用对应的类型标识符代替
计 算 机 软 件 基 础 • 二叉链表中结点类型的定义： 注意：datatype在此处代表任意数据类型，实现时应根 据结点的实际数据类型用对应的类型标识符代替。 lchild data rchild 计 算 机 软 件 基 础 typedef struct node { datatype data; struct node * lchild,* rchild; }bstree；