|
|
知识路径： > 计算机系统基础知识 > 计算机软件基础知识 > 数据结构与算法 > 常用数据结构 > 树和图 > 树 >
|
|
相关知识点：7个
|
|
|
|
|
|
|
用一组地址连续的存储单元存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑关系。对于深度为k的完全二叉树，除第k层外，其余各层中含有最大的结点数，即每一层的结点数恰为其上一层结点数的两倍，由此从一个结点的编号可推知其双亲、左孩子和右孩子的编号。
|
|
|
|
|
.若i=1，则该结点为根结点，无双亲；若i>1，则该结点的双亲结点为 。
|
|
|
|
.若2i≤n，则该结点的左孩子编号为2i，否则无左孩子。
|
|
|
|
.若2i+1≤n，则该结点的右孩子编号为2i+1，否则无右孩子。
|
|
|
|
|
|
|
|
|
|
显然，顺序存储结构对完全二叉树而言既简单又节省空间，而对于一般二叉树则不适用。因为在顺序存储结构中，以结点在存储单元中的位置来表示结点之间的关系，那么对于一般的二叉树来说，也必须按照完全二叉树的形式存储，也就是要添上一些实际并不存在的“虚结点”，这将造成空间的浪费，如上图（b）所示。
|
|
|
|
在最坏的情况下，一个深度为h且只有h个结点的二叉树（单枝树）却需要2h-1个存储单元。
|
|
|
|
|
|
由于二叉树中结点包含有数据元素、左子树根、右子树根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有三个指针或两个指针）来存储二叉树，链表的头指针指向二叉树的根结点，如下图所示。
|
|
|
|
|
|
|
|
设结点中的数据元素为整型，则二叉链表的结点类型定义如下：
|
|
|
|
|
