清远网站制作公司,江门网站建设报价,手机企业管理app软件,百度搜索简洁版网址二叉树的存储结构
二叉树一般可以使用两种结构存储#xff0c;一种是顺序结构#xff0c;另一种是链式结构。
一、顺序存储 二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素#xff0c;即将完全二叉树上编号为i的结点元素存储…二叉树的存储结构
二叉树一般可以使用两种结构存储一种是顺序结构另一种是链式结构。
一、顺序存储 二叉树的顺序存储是指用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素即将完全二叉树上编号为i的结点元素存储在一维数组下标为i-1的分量中。
依据二叉树的性质完全二叉树和满二叉树采用顺序存储比较合适树中结点的序号可以唯一地反映结点之间的逻辑关系既最大可能地节省存储空间且可以利用数组元素的下标值确定结点在二叉树中的位置以及结点之间的关系。但对于一般的二叉树为了让数组下标能反映二叉树中结点之间的逻辑关系只能添加一些并不存在的空结点大让其每个结点与完全二叉树上的结点相对照再存储到一维数组的相应分量中。
实际就是使用数组来存储一般使用数组只适合表示完全二叉树因为非完全二叉树会有空间的浪费。而现实使用中只有堆才会使用数组来存储。所以二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。
例二叉树的顺序存储中一定要把二叉树的节点编号与完全二叉树对应起来
* i的左孩子 ——2i
* i的右孩子 ——2i1
* i的父节点 ——[i/2]
在最坏情况下高度为h且只有h个结点的单支树所有结点只有右孩子也至少需要2h-1个存储单元。其中0表示并不存在的空结点。
结论二叉树的顺序结构只适合存储完全二叉树。 二叉树的顺序存储结构描述如下:
#define MAXSIZE 20
typedef struct BiTNode {
ElemType data; //数据域
int 1child, rchild; //存放左、右孩子的数组下标
}BiTNode; //二叉树节点的类型BiTNode tree[MAXSIZE];
int n; //树中实际所含节点的个数
int root; //存放根节点的数组下标 二、链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域 (data)和左(lchild)、右(rchild)指针域左、右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 二叉树的链式存储结构描述如下:
typedef struct BiTNode {
ElemType data;//数据域
struct BiTNode *1child, *rchild;//左、右孩子指针
}BiTNode, *BiTree; 所以使用不同的存储结构时实现二叉树操作的算法也会不同因此要根据实际应用场合二叉树的形态和需要进行的运算来选择合适的存储结构。容易验证在含有n个结点的二叉链表中含有n 1个空链域
