联博以太坊:二叉树的存储结构

admin 2周前 (09-09) 科技 47 1

二叉树的存储结构

二叉树可使用顺序结构和链表结构两种存储结构

顺序结构

顺序结构实现二叉树时,接纳一个一维数组来存储所有结点,需要将所有结点根据在树中的位置安排成一个适当的序列,使其能反映结点之间相互的逻辑关系,通常使用编号的方式;

具体方式:

将二叉树中所有结点根据完全二叉树举行编号,然后使用一维数组存储,同时使结点编号与数组下标相同,如编号为1的节点存储在数组下标为1的位置;该方式称为以编号为地址的计谋

案例1(完全二叉树):

若二叉树为完全二叉树则上述方式,可以很好的行使存储空间,基本没有虚耗,且对于结点的查找是很利便的;

案例2(一样平常二叉树):

当二叉树为一样平常二叉树时,如想要使用顺序结构存储则必须增添虚拟结点,使其变为完全二叉树,像下面这样:

这样一来则需要虚耗一部门存储空间,极端情况下,若二叉树是一分叉的(每个节点只有一个子节点),将造成极大的空间虚耗

联博以太坊:二叉树的存储结构 第1张

链式存储结构

链式存储结构,分为两种二叉链表和三叉链表

二叉链表

每个结点由一个数据域和两个指针域组成,共三个部门,如下图所示

联博以太坊:二叉树的存储结构 第2张
数据结构界说:
typedef struct btnode {
	DataType data;
	struct btnode *lchild,*rchild;
}*BinTree;
案例:
联博以太坊:二叉树的存储结构 第3张

由于使用了链式存储结构,在插入或删除结点时效率比顺序结构更好;而且不会造成较大的空间虚耗;

特征:
  • n个结点组成的二叉树共有2n个指针域,其中有n-1个指向左右子结点的非空指针域,(两个节点关联需要一个指针域,以此类推3个结点关联需要2个指针域)和n+1个空指针域
  • 已知某结点地址求其子结点利便,求其父节点则需要从头开始遍历

三叉链表

由于二叉链表查找父结点需要遍历所有结点,效率较低,若对于经常需要查询父结点的二叉树,则可以使用三叉链表来提高效率,三叉链表在二叉链表的基础上增添了一个parent指针域,如下图所示:

联博以太坊:二叉树的存储结构 第4张
案例:
联博以太坊:二叉树的存储结构 第5张 可以看出三叉链表与二叉链表没有太大区别,牺牲一些空间换来了查询父结点的效率;,

SuNBet

Sunbet秉承以客为先的理念,多年运营、专业团队、专注服务、值得信赖。

AllBetGaming声明:该文看法仅代表作者自己,与本平台无关。转载请注明:联博以太坊:二叉树的存储结构

网友评论

  • (*)

最新评论

  • 欧博allbet网址 2020-09-09 00:11:17 回复

    欧博app下载欢迎进入欧博app下载网站:www.aLLbetgame.us,欧博app下载网站是欧博官方网站。欧博app下载网站开放欧博注册、欧博代理、欧博电脑客户端、欧博app下载等业务。语言是苍白的,好啊

    1

站点信息

  • 文章总数:658
  • 页面总数:0
  • 分类总数:8
  • 标签总数:1144
  • 评论总数:222
  • 浏览总数:10179