qq_43412960
2020-04-26 22:58
采纳率: 50%
浏览 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区分，是孩子还是线索。

    评论
    解决 无用
    打赏 举报

报告相同问题？

提交

相关推荐 更多相似问题

  • 这是一个关于数据结构二叉树的内容 c++
    2020-04-26 22:58
    回答 1 已采纳 ![图片说明](https://img-ask.csdn.net/upload/202004/27/1587918519_611968.png) 看这个图，比如说先序遍历 传统的，每个节点存储左右
  • 这是一个关于数据结构二叉树遍历的问题 c++
    2020-04-22 12:59
    回答 2 已采纳 你好呀，这个问题属于 中缀表达式 和 前缀表达式（也称波兰式）的相互转换。 以下是我的纸质演算过程。 ![图片说明](https://img-ask.csdn.net/upload/20200
  • 这是一个关于数据结构二叉树的遍历问题 c++
    2020-04-25 08:17
    回答 4 已采纳 拿 https://blog.csdn.net/qq_44556821/article/details/96423326 这个程序改了下。 ``` #include #include us
  • 根据二叉树的抽象数据类型的定义，使用二叉链表实现一个二叉树。
    2018-12-07 22:43
    二叉树的基本功能： 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他：自定义操作
  • Python 数据结构之队列的实现
    2020-12-25 07:37
    queue = [] # 初始化一个列表数据类型对象, 作为一个队列 def enQ(): # 定义一个入栈方法 queue.append(raw_input('Enter New String: ').strip()) # 提示输入一个入队的 String 对象, 调用 Str.strip() 保证输入...
  • 数据结构——计算节点个数和二叉树高度（C语言版）
    2020-12-12 23:27
    正弦定理的博客 数据结构——计算节点个数、二叉树高度一、计算各种节点（1）计算总节点：（2）计算单分支节点：（3）计算双分支节点：二、计算二叉树高度代码实现： 一、计算各种节点 二叉树结构体如下： // 二叉树结构体 ...
  • 这是一个关于数据结构二叉树的相关知识 c++
    2020-04-29 23:45
    回答 3 已采纳 这个和你的使用场景有关。 有时候需要顺序，有时候不需要。 比如说二元运算 a+b和b+a满足交换律，那么顺序就不重要。 a ** b（表示a的b次方）、a/b，不满足，顺序就很重要。 如
  • 这是一个关于数据结构线索二叉树的算法问题 c++
    2020-04-25 23:32
    回答 1 已采纳 思想就是，如果我们要遍历一个二叉树，需要一个堆栈。 遍历一个“一叉树“（你可以把链表或者顺序表也看作二叉树特例，只是它所有节点的度都是1）不需要堆栈 为什么呢，因为当出现2个分支的时候，我们必须先
  • 这是一个数据结构二叉树问题 c++
    2020-04-21 23:05
    回答 1 已采纳 ![图片说明](https://img-ask.csdn.net/upload/202004/22/1587484886_989524.png) 任何一个二叉树都可以通过上面的图生成（当然，单个节点
  • 数据结构与算法 python语言描述 裘宗燕
    2019-01-29 00:37
    本书基于Python语言介绍了数据结构与算法的基本知识，主要内容包括抽象数据类型和Python面向对象程序设计、线性表、字符串、栈和队列、二叉树和树、集合、排序以及算法的基本知识。本书延续问题求解的思路，从解决...
  • 数据结构学习笔记（六）：二叉树（Binary Tree）
    2021-06-13 01:36
    文程公子的博客 1 树与二叉树的概念 1.1 树的概念 前面笔记中介绍的链表、栈、队列、数组和字符串组织数据的方式都是
  • C语言实现二叉树的遍历（数据结构）
    2021-10-26 23:33
    码猿小菜鸡的博客 二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树 二叉树的性质 二叉树遍历 二叉树有三种遍历方式，...
  • 这是一个数据结构二叉树的相关问题 c++
    2020-04-30 13:31
    回答 3 已采纳 递归遍历代码简洁，首先推荐 非递归遍历，不受递归深度限制，效率高，如果前者性能遇到问题，再用这个办法, 这也是一个原则性，你应该了解 编写程序的一般做法是，先用最简单的方式实现出来，再对
  • 数据结构（c＋＋语言）求二叉树的宽度 c++数据结构有问必答
    2021-11-15 18:49
    回答 1 已采纳 参考： #include<iostream> #include<stdlib.h> #include<deque> //插入标准库中的头文件 using nam
  • 菜鸟#c语言数据结构#二叉树 c语言
    2019-06-01 22:46
    回答 1 已采纳 程序没有根本性的错误，只是数组下标从0而不是1开始算 ``` // Q764195.cpp : This file contains the 'main' function. Prog
  • 数据结构二叉树
    2011-12-14 13:17
    数据结构的二叉树编程，C++语言，课程实例，自己编的哦，仅供参考
  • SCAU 数据结构 18924 二叉树的宽度
    2021-04-28 21:35
    SCAU-山竹的博客 SCAU 数据结构 18924二叉树的宽度 时间限制:1000MS 代码长度限制:10KB 提交次数:0 通过次数:0 题型: 编程题语言: 不限定 Description 二叉树的宽度指的是具有节点数目最多的那一层的节点个数。 1 / \ 2 3 ...
  • 数据结构与算法——二叉树
    2020-10-20 23:39
    Myster_KID的博客 文章目录二叉树二叉树的存储结构链式存储结构二叉树的算法设计用字符串建立二叉树什么是括号表示法？代码实现销毁二叉树求高度（深度）求结点个数求叶子结点个数以括号表示法输出二叉树遍历先序遍历中序遍历后序遍历...
  • 这是一个关于数据结构的递归问题 c++
    2020-04-30 16:51
    回答 2 已采纳 就是转换成堆栈，如果你要一个通用的办法，那么就相当于实现一个解释器。因为解释器就维护一个通用的调用堆栈。
  • 【经典回放】多种语言系列数据结构算法：二叉树（C#版）
    2020-06-12 21:07
    刘一哥GIS的博客 1 用C#语言完成二叉树的类、并构造出一个二叉树； 2 用递归方法完成二叉树的遍历； 3 泛型的二叉树遍历之一、用队列给出遍历结果 4 泛型的二叉树遍历之二、委托方式给出二叉树遍历结果 1 二叉树类的设计 同...
  • 没有解决我的问题, 去提问