qq_43412960 2020-04-26 22:58 采纳率: 78.6%
浏览 71
已采纳

这是一个关于数据结构二叉树的内容

线索二叉树怎么充分利用了剩余结点呢?把剩余结点记录前驱后继,有什么效果呢?
课本上说,把树形逻辑变为线性逻辑,这一点如何体现的呢?

  • 写回答

1条回答 默认 最新

  • threenewbee 2020-04-27 00:34
    关注

    图片说明
    看这个图,比如说先序遍历
    传统的,每个节点存储左右孩子(蓝色线)
    1->2->3没问题,3回不到2了。怎么办,需要在访问2的时候,把2放入堆栈。访问完3,左右都没有孩子了,此路走完,再到堆栈里面找2,才能到4。
    类似的,4到1也不能直接连上。6到5也不能连上。
    怎么办?
    增加一个"线索",红色的箭头,在3的节点上指向2,4指向1,6指向5。
    这样,不需要堆栈就可以遍历了。
    图片说明
    没有线索,遍历需要4个序列。
    现在用红色绳子把这4列串成一条线,这就是线索。
    什么地方需要添加“线索”?没有左右孩子的节点,所以为了节约存储,可以把线索和孩子的节点放在同样的存储单元,用一个flag区分,是孩子还是线索。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥100 将USDZ文件转化为带颜色的OBJ文件
  • ¥15 对象代号: , 表单: 不存在!
  • ¥15 WebSocket的问题
  • ¥15 centos上启动kylin后网页报错404
  • ¥20 使用hackrf进行信号收发时接收到的信号幅度太小
  • ¥15 WebSocket的问题
  • ¥15 BDSBAS-B1C和B1C信号有什么不同
  • ¥15 在半圆平面内随机生成点坐标
  • ¥15 系统容量变化的几种多址方式TDMA, CDMA,FDMA,OFDMA 对比,应该给的是一个曲线 图,随着系统容量的增加,几种多址方式性能的对比 图,MATLAB程序仿真折线图
  • ¥15 用visual Studio 写c ++只运行上一个旧代码的运行结果是怎么回事