数据结构——二叉树的存储结构举例

杨伟彬
杨伟彬   编辑于 2018-12-07 14:04
阅读量: 72

1. 二叉树的定义

定义

        二叉树是 n (n≥0) 个结点的有限集,它或者是空集 (n = 0),或者由一个根结点及两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成。

特点:

              ①每个结点最多有俩孩子 (二叉树中不存在度大于 2 的结点);

              ②子树有左右之分,其次序不能颠倒;

              ③二叉树可以是空集合,根可以有空的左子树或空的右子树。

注意:

        二叉树不是树的特殊情况。二叉树结点的子树要区分左子树和右子树,即使只有一棵子树也要进行区分,说明它是左子树,还是右子树。树当结点只有一个孩子时,就无须区分它是左还是右。(也就是二叉树每个结点位置或者说次序都是固定的,可以是空,但是不可以说它没有位置,而树的结点位置是相对于别的结点来说的,没有别的结点时,它就无所谓左右了),因此二者是不同的。这是二叉树与树的最主要的差别。 

形态:

       上面是二叉树的5种基本形态,虽然二叉树与树概念不同,但有关树的基本术语对二叉树都适用。

        一棵深度为k且有\(2^k-1\)个结点的二叉树称为满二叉树

        深度为k的具有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号为1~ n的结点一一对应时,称之为完全二叉树。    

2. 顺序存储结构

       完全二叉树:用一组地址连续的存储单元依次自上而下、自左至右存储结点元素,即将编号为i的结点元素存储在一维数组中下标为i–1的分量中。

        一般二叉树:将其每个结点与完全二叉树上的结点相对照,存储在一维数组的相应分量中。

 

        对于非完全二叉树,在最坏的情况下,一个深度为k且只有k个结点的单支树却需要长度为的一维数组,造成很大空间浪费。因此,这种顺序存储结构仅适用于完全二叉树。顺序存储结构如下:

#define  MAX_TREE_SIZE 100					  // 二叉树的最大结点数 
typedef  TElemType  SqBiTree[MAX_TREE_SIZE];//0号单元存储根结点                                
SqBiTree  bt;

3. 链式存储结构

       用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为:

        其中,data域存放某结点的数据信息;lchild与rchild分别存放指向左孩子和右孩子的指针,当左孩子或右孩子不存在时,相应指针域值为空。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表,如下图所示:

 

        由上图可知,在n个结点的二叉链表中有n + 1个空指针域。因为n个结点有2n个指针域,其中用了n - 1指针域(头结点没用指针域)。二叉树的二叉链表存储表示如下:

//二叉树的二叉链表存储表示
typedef struct BiTNode
{
	TElemType data;
	struct BiTNode *lchild ,*rchild;	//左右孩子指针
}BiTNode,*BiTree;

 

收藏 转发 评论