目 录CONTENT

文章目录

数据结构中的树存储结构,树/二叉树

Hello!你好!我是村望~!
2022-08-11 / 2 评论 / 0 点赞 / 440 阅读 / 988 字
温馨提示:
我不想探寻任何东西的意义,我只享受当下思考的快乐~

理解树结构

树结构通常用来存储逻辑关系为 “一对多” 的数据。

image-1660176544646
image-1660117542769

的这些元素具有的就是 “一对多” 的逻辑关系,例如元素 A 同时和 B、C、D 有关系,元素 D 同时和A、H、I、J有关系等。 观察这些元素之间的逻辑关系会发现,它们整体上很像一棵倒着的树(将图 1b) 倒过来),这也是将存储它们的结构起名为“树”(或者 “树形”)的原因。

存储具有 “一对多” 逻辑关系的数据,数据结构推荐使用树存储结构。

与树相关的术语

数据结构中的树,首先是对现实世界中树的一层简化:

抽象后的树结构如下:
把这棵抽象后的树颠倒一下,就得到了计算机中的树结构:

  • 树的根节点,叶子节点(不能分叉的节点)
  • 树的深度
    image-1660182058499
  • 树的度:整个树里(包括根节点在内),节点分叉最多的度!就是树的度!
  • 孩子节点、父节点(类似族谱去理解)
  • 子树 (族谱,比如儿子的新家庭,那么儿子下面就构成了一个新的子树)
    image-1660176704653

理解二叉树结构

二叉树,就是度不超过2的树!
它可以没有根结点,作为一棵空树存在

如果它不是空树,那么必须由根结点、左子树和右子树组成,且左右子树都是二叉树。如下图:
image-1660182750577

注意,二叉树不能被简单定义为每个结点的度都是2的树普通的树并不会区分左子树和右子树,但在二叉树中,左右子树的位置是严格约定、不能交换的。对应到图上来看,也就意味着 B 和 C、D 和 E、F 和 G 是不能互换的。(按照顺序从左到右!)

满二叉树

一个树,如果每一层的节点数都达到最大值2,则这个二叉树为满二叉树!

完全二叉树

叶结点只能出现在最下层和次下层,并且最下面一层的节点,都集中在该层最左边的若干位置的二叉树!

image-1660183542029

二叉树的存储方式!

二叉树的存储方式分为两种

一个是顺序存储

顺序存储:数组方式存储,表现上是一个一维数组,逻辑上是一颗二叉树

image-1660184569566

  • 圆圈顶部的数字对应了数组中的索引
  • 圆圈内部的值对应的数数组元素的值

规律思考:

  1. 父节点i(这个i指的是顺序存储的索引)和左孩子节点的编号下标有什么关系?
    0-1 1-3 2-5 存在 2i+1 的数学规律!
  2. 父节点i和右孩子节点的编号下标有什么关系?
    那么知道了父节点和左孩子节点的规律,那么右孩子其实就是多一个位置 那么就是2i+2
  3. 通过子节点的索引i找到父节点的规律?
    1,2-0 3,4-1 5,6-2 如果子节点-1然后整除(除完取整)比如(1-1/2 = 0;2-1/2 = 0.x0.x取整也为0)所以父节点就是在数组中索引为0的,其他的也是一样的!

另一个是链表存储(这个我还没有学)

链表存储:采用链表的方式进行存储,链表包含逻辑关系,左指针,右指针。从表现到逻辑都是一颗二叉树。

0

评论区