二叉树的存储结构

深藏阁楼爱情的钟 2021-10-18 12:00 472阅读 0赞

二叉树的存储-顺序存储

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

![1736739-20190719222741456-1034916964.png][]

特点：

结点间关系蕴含在其存储位置中（性质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

![1736739-20190719223824288-854444998.png][]

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

![1736739-20190719223948463-1955398217.png][]

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

![1736739-20190719224151178-1087527301.png][]

二叉树的存储-链式存储（1）

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

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

ypedef struct BiTnode

\{TElemType data;

struct BiTNode \*Lchild, \*rchild;

\}BiTNode,\*BiTree;

lchild　　data　　rchild

data

↙               ↘

lchild　　　　　　rchild

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

三叉链接

![1736739-20190719224944343-638270902.png][]

转载于:https://www.cnblogs.com/privilege/p/11216116.html

[1736739-20190719222741456-1034916964.png]: /images/20211018/156b56c83ae44fecb2c397ffe7bcaa5d.png
[1736739-20190719223824288-854444998.png]: /images/20211018/bd0e513784164a5cb4847e8cce03f92d.png
[1736739-20190719223948463-1955398217.png]: /images/20211018/ee45591870ed4954a7e56f1df4fc9790.png
[1736739-20190719224151178-1087527301.png]: /images/20211018/b61ec5f1fa2347c4bf2bb4fcd7a0a0b4.png
[1736739-20190719224944343-638270902.png]: /images/20211018/7effac27c25f41d79fdab8a0bb84cffb.png

发表评论取消回复

表情：

评论列表（有 0 条评论，472人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构】图解二叉树的存储结构

文章目录二叉树的顺序存储结构二叉链表二叉树的顺序存储结构二叉树的存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也

迷南。/ 2023年02月19日 11:24/ 0 赞/ 124 阅读

相关二叉树的存储结构

`本文主要为观看哔哩哔哩视频网站上的王道考研的数据结构的学习笔记，如有侵权，请联系我删除` 顺序存储 ![在这里插入图片描述][watermark_type_ZmFuZ

男娘i/ 2023年01月07日 13:30/ 0 赞/ 123 阅读

相关二叉树的存储结构

一概述二叉树的存储结构可以分为顺序存储和链式存储两种存储结构。二顺序存储结构二叉树的顺序存储结构是指用一组地址连续的存储单元依次自上而下，自左至右存储完

谁践踏了优雅/ 2022年12月09日 01:52/ 0 赞/ 182 阅读

相关二叉树的存储结构（数据结构）

1. 链式存储结构即单链表结构或双链表结构（同树）。数据结构修改如下： typedef struct node; type

港控/mmm°/ 2022年06月09日 06:48/ 0 赞/ 256 阅读

相关数据结构——树—— 二叉树及存储结构

在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查

电玩女神/ 2022年04月16日 04:06/ 0 赞/ 286 阅读

相关二叉树的存储结构

二叉树的存储有顺序存储结构和链式存储结构其中顺序存储结构造成了很大的资源浪费。 ![70][] ![70 1][] ![70 2][] [70]: /images

àì夳堔傛蜴生んèń/ 2022年04月13日 06:37/ 0 赞/ 222 阅读

相关二叉树的存储结构类型

存储结构类型顺序存储结构描述对象

怼烎@/ 2022年02月05日 10:47/ 0 赞/ 209 阅读

相关二叉树的存储结构

二叉树的存储结构有两种：顺序存储结构和链式存储结构。顺序存储结构对于满二叉树和完全二叉树来说，可以将其数据元素逐层存放到一组连续的存储单元中，如图6-3 所示。用一维数

青旅半醒/ 2022年01月11日 17:23/ 0 赞/ 314 阅读

相关数据结构--二叉树的存储结构

文章目录顺序存储表示链式存储表示二叉链表三叉链表顺序存储表示以存储的数据是整型为例。 // 二叉树的最

r囧r小猫/ 2022年01月07日 17:53/ 0 赞/ 364 阅读

相关二叉树的存储结构

二叉树的存储-顺序存储完全二叉树：对结点按照上至下、从左到右的次序进行存储 ![1736739-20190719222741456-1034916964.png][]

深藏阁楼爱情的钟/ 2021年10月18日 12:00/ 0 赞/ 473 阅读