专栏首页孙小白树的存储、森林的存储

树的存储、森林的存储

树的存储:

  二叉树的存储:

    1. 连续存储(顺序存储)【完全二叉树】,以数组实现

      优点:

        查找某个节点的父节点和子节点(包括判断有没有子节点和父节点)

      缺点:

        耗用内存空间过大

    2. 链式存储:

      一个节点包含三个部分:左子节点地址、数据域、右子节点地址

      优点:耗内存小

  一般树的存储:

      由于计算机的内存是线性的,而树是非线性的。若在计算机里只存树的有效节点,便不能查找某个节点的子节点和父节点(或者说整个树的逻辑存储无法知晓),所以必须要先转化成完全二叉树,把垃圾节点补上。

绿色的是普通树,蓝色的是转为满二叉树,黄色的是去掉了底层连续的叶子节点,即成了完全二叉树

双亲表示法:

由于树中的每个结点都有唯一的一个双亲结点,所以可用一组连续的存储空间(一维数组)存储树中的各个结点,数组中的一个元素表示树中的一个结点,每个结点含两个域,数据域存放结点本身信息,双亲域指示本结点的双亲结点在数组中位置(下标)。方便查询某结点的父结点

孩子表示法:

将树中的每个结点的孩子结点排列成一个线性表,用链表存储起来。对于含有 n 个结点的树来说,就会有 n 个单链表,将 n 个单链表的头指针存储在一个线性表中,这样的表示方法就是孩子表示法。如果结点没有孩子(例如叶子结点),那么它的单链表为空表。方便查询某结点的子节点

双亲孩子表示法:

  方便查询某结点的子节点和父节点

二叉树表示法(孩子兄弟表示法):

把一个普通树转化成二叉树来存储,此二叉树的根节点没有右子树

使用链式存储结构存储普通树。链表中每个结点由 3 部分组成:

其中孩子指针域,表示指向当前结点的第一个孩子结点,兄弟指针域表示指向当前结点的下一个兄弟结点。

森林的存储:

先把森林转化为二叉树,再存储二叉树

跟一般树转化为二叉树的过程相似,把不相交的根节点视为兄弟节点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 层次模型(树形结构)

    在层次模型中,每个结点表示一个记录类型,每个记录类型可包含若干个字段,记录类型描述的是实体,字段描述的是实体的属性。

    爱学习的孙小白
  • 链表的定义、确定一个链表需要几个参数?

        N个节点离散分配 彼此通过指针相连 每个节点只有一个前驱节点,每个节点只有一个后驱节点。 首节点没有前驱节点,尾节点没有后续节点

    爱学习的孙小白
  • 树的定义以及相关专业术语

    双亲结点或父节点(parent):若一个节点含有子节点,则这个节点称为其子节点的父节点

    爱学习的孙小白
  • 绝对均匀图生成算法

    最近在研究图计算的性能,需要构造不同的测试数据对图算法进行压测,其中就涉及到均匀图的概念。

    Florian
  • 【数据结构】单链表操作

    链表的逆转在上一次文章中发布了,这次将给大家分享链表的4个基本操作,即增、删、改、查;基本的创建链表,以及输出链表的函数操作的写法在此就不再详细写出,详细参...

    程序员周同学
  • 数据结构 | 每日一练(37)

    ——老子

    闫小林
  • 初探Java源码之LinkedList

    上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

    Java后端技术
  • 小文’s blog — 平衡二叉树构造方法

    神无月
  • 请你对Java中树的了解有多少?

    树 1200101班的学生信息表如图6.1所示,其中学生被分到了不同的学习小组,第一组组长是李华,组员有王丽、张阳、赵斌; 第二组组长是孙琪,组员有马丹; 第三...

    Java学习
  • 二叉树性质

    •【性质1】在二叉树的第i层上最多有2i-1个结点(i>=1)。 【性质2】深度为k的二叉树至多有2k –1个结点(k>=1)。 •【特别】一棵深度为k且有2k...

    attack

扫码关注云+社区

领取腾讯云代金券