二叉树的存储结构
发表时间：2020-10-18
发布人：葵宇科技
浏览次数：26
1）二叉树的存储存储结构
用一组地址连续的存储单元（一维数组）存储二叉树中的结点，必须把结点排成一个适当的线性序列，并且结点在这个序列中的相互位置能反映出结点之间的逻辑头系。
对于深度为k完全二叉树，除第k层外，其余各层中含有最大的结点数，即每一层的结点数恰为其上一层结点数的两倍。因此，从一个结点的编号可推知其双亲、左孩子和右孩子的编号。
假设有编号为i的结点，则有：
1.若i=1时，该结点为根结点，无双亲。
2.若i>1时，该结点的双亲结点为[（i+1)/2]。
3.若2i≤n,则该结点的左孩子编号为2i，否则无左孩子。
4.若2i+1≤n,则该结点的右孩子编号为2i+1,否则无右孩子。
完全二叉树的顺序存储结构。
完全二叉树采用顺序存储既简单又节省空间，而一般的二叉树则不宜用顺序存储结构，因为需要添加一些实际并不存在的虚结点将造成空间的浪费，在最坏情况下，一个深度为k且只有k个结点的二叉树（单支树）需要2k-1个存储单元。
（2）二叉树的结点包含数据元素、左子树的根、右子树的根及双亲等信息，因此可以用三叉链表或二叉链表（即一个结点含有三个指针或两个指针）来顾念二叉树，链表的头指针指向二叉树的根结点。
设结点中的数据元素为整型，则二叉链表的结点类型定义如下：
typedef struct BiTnode
int data；
在不同的顾念结构中，实现二叉树的远算方法是不同的。具体应采用什么存储结构，除了考虑二叉树的形态外，还应考虑需要进行的运算特点。
