首页 > 其他 > 详细

二叉树的存储结构

时间:2019-07-19 23:41:20      阅读:91      评论:0      收藏:0      [点我收藏+]

二叉树的存储-顺序存储

完全二叉树:对结点按照上至下、从左到右的次序进行存储

技术分享图片

特点:

结点间关系蕴含在其存储位置中(性质5)

1、非根结点i的父结点序号为[i/2]

2、结点i的左孩子序号为2i

3、结点i的右孩子序号为2i+1

 适用于满二叉树和完全二叉树

 

二叉树性质5

如果对一棵有n个结点的完全二叉树的结点按层序编号,则对任一结点i(1<=i<=n),有:

1、如果i=1,则结点i是二叉树的根,无双亲;

如果i>i,则其双亲是[i/2]

2、如果2i>n,则结点i无左孩子;

如果2i<=n,则其左孩子是2i

3、如果2i+1>n,则结点i无右孩子;如果2i+1<=n,则其右孩子是2i+1

技术分享图片

 

 一般二叉树也可以采用顺序存储结构,但会造成空间的浪费

技术分享图片

 

 深度为k且只有k个节点的单支树,需要长度为2(k-1)次方的一维数组

技术分享图片

 

 二叉树的存储-链式存储(1)

二叉树结点由一个数据元素和分别指向其左、右子树和两个分支构成

表示二叉树的链表中的结点至少包含3个域:数据域和左、右指针域

ypedef struct BiTnode

{TElemType data;

struct BiTNode *Lchild, *rchild;

}BiTNode,*BiTree;

 

lchild  data  rchild

    data

       ↙               ↘

lchild      rchild

 

有时,为了便于找到结点的双亲,在结点结构中增加一个指向其双亲结点的指针域

三叉链接

技术分享图片

 

二叉树的存储结构

原文:https://www.cnblogs.com/privilege/p/11216116.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!