看这个图，比如说先序遍历
传统的，每个节点存储左右孩子（蓝色线）
1->2->3没问题，3回不到2了。怎么办，需要在访问2的时候，把2放入堆栈。访问完3，左右都没有孩子了，此路走完，再到堆栈里面找2，才能到4。
类似的，4到1也不能直接连上。6到5也不能连上。
怎么办？
增加一个"线索"，红色的箭头，在3的节点上指向2，4指向1，6指向5。
这样，不需要堆栈就可以遍历了。
没有线索，遍历需要4个序列。
现在用红色绳子把这4列串成一条线，这就是线索。
什么地方需要添加“线索”？没有左右孩子的节点，所以为了节约存储，可以把线索和孩子的节点放在同样的存储单元，用一个flag区分，是孩子还是线索。
这是一个关于数据结构二叉树的内容
5 已采纳
线索二叉树怎么充分利用了剩余结点呢？把剩余结点记录前驱后继，有什么效果呢？
课本上说，把树形逻辑变为线性逻辑，这一点如何体现的呢？
- 点赞
- 写回答
- 关注问题
- 收藏
- 复制链接分享
- 邀请回答
1条回答
-
采纳
点赞 1 评论 复制链接分享
提交
相关推荐
- 回答 4 已采纳 二叉树非递归中序遍历，思路是啥呢？ 我想敲出代码来，但是想不通这种分叉的东西怎么写，也想不透怎么把根节点的位置顺序体现出来
- 回答 2 已采纳 ``` a+b*(c-d)-e/f ``` 的先序是 ``` -+a*b-cd/f ``` 请问这是如何推到出来的呢？ 先序，我个人认为是把运算符都放最前面，但是并没有那样，字母中间还放了一些，迷茫，求解
- 1年前回答 1 已采纳 线索二叉树怎么充分利用了剩余结点呢？把剩余结点记录前驱后继，有什么效果呢？ 课本上说，把树形逻辑变为线性逻辑，这一点如何体现的呢？
- 回答 3 已采纳 二叉树的子树有左右之分，其次序不能任意颠倒。这是为什么呢？ 要求次序，非要整的特别严格干嘛。。感觉二叉树结点就是以一个个离散的结点组合的，根本看不出来哪个是左子树，哪个是右子树
- 1年前回答 1 已采纳 对任何一颗二叉树T，如果其终端节点数为n0,度为2的节点数为n2，则n0=n2+1 这是为什么呢？求大佬们帮忙解答！另外，满二叉树和完全二叉树区别是？
- 1年前回答 3 已采纳 二叉树的递归遍历，其实是采用栈结构,因为递归就是栈里进行操作嘛。 二叉树的非递归遍历，也采用了栈结构，我分不清两个遍历方法，哪个更好，求解
- 回答 1 已采纳 线索二叉树，设计的思想是什么呢？不用帮我写代码，告诉我思想就行了。比如，用递归算法完成遍历子树功能，我课本有代码，但是看不懂 。，，
- 3年前回答 1 已采纳 小白刚学..可能错误有点多，求大神解答 错误提示： error C2146: syntax error : missing ';' before identifier 'A' error C2501: 'St' : missing storage-class or type specifiers fatal error C1004: unexpected end of file found 求二叉树宽度.exe - 1 error(s), 0 warning(s) #include #include #define maxsize 20 St A[maxsize]; int L=1;//记录层数 int i=0; void width(BTNode *p); BTNode *CreateBiTree(); void main() { int j,k=0; int max=0; BiTree T; T = CreateBiTree();//建立 width(T); for(j=0;jmax?k:max); } else k=1; } printf("%d\n",max); } typedef struct BTNode{ int data; struct BTNode *lchild,*rchild; }BTNode; //先序建立二叉树 BTNode *CreateBiTree(){ char ch; BTNode *T; scanf("%c",&ch); if(ch=='#')T=NULL; else{ T = (BTNode *)malloc(sizeof(BTNode)); T->data = ch; T->lchild = CreateBiTree(); T->rchild = CreateBiTree(); } return T;//返回根节点 } typedef struct { BTNode *q; int level; }St; void width(BTNode *p) { A[i].q=p; A[i].level=L; ++i; ++L; width(p->lchild); width(p->rchild); --L; }
- 5年前回答 5 已采纳 一个对象何时可以通过成员运算符调用private变量，何时不可以？。。。。。。。。
- 回答 4 已采纳 class twopoint{ protected: double x,y; public: twopoint(double i,double j):x(i),y(j){ } void setX(double NewX) { x=NewX; } void setY(double NewY){ y=NewY; } double getX()const{return x;} double getY()const{return y;} }; 最后两行的 double getX()const{return x;}，double getY()const{return y;}，那个const有什么作用的，书本没提到。。
- >=FreeMan=<的博客 分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 平衡二叉树的定义 平衡二叉树（Balanced Binary Tree）是具有以下性质的二叉树：...
- 2年前>=FreeMan=<的博客 完全二叉树是一种效率很高的数据结构，堆就是一种完全二叉树，效率极高。像十分常用的排序算法、Dijkstra算法、Prim算法等等都要用堆才能优化；经常提到的二叉排序树的效率也要借助平衡性来提高，而平衡性基于完全...
- 2年前>=FreeMan=<的博客 分享一个大牛的人工智能教程。零基础！通俗易懂！风趣幽默！希望你也加入到人工智能的队伍中来！请点击http://www.captainbed.net 二叉树的遍历 N：访问根结点，L：遍历根结点的左子树，R：遍历根结点的右子树。 ...
- 3年前阿云_的博客 一、树的定义树是一种数据结构，它是由n（n&amp;amp;gt;=1）个有限结点组成一个具有层次关系的集合。&amp;amp;nbsp;树具有的特点有：（1）每个结点有零个或多个子结点（2）没有父节点的结点称为根节点（3）...
- 3年前夜雨柠檬的博客 = 0）个节点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两颗互不相交的，分别称为根节点的左子树和右子树的二叉树组成。二叉嘛，也就是每个节点最多有两个分支。图示：二叉树具有五种基本...
- 3年前顾小豆的博客 文章开头首先要感谢一下国嵌嵌入式教育的工作者们。...1. 顺序存储结构：按照顺序存储结构的定义，在此约定用一组地址连续的存储单元一次自上而下、自左至右存储完全二叉树上的节点元素，即将完全二叉...
- 5月前木_卜的博客 C语言-二叉树-基本程序代码一些基本操作定义二叉树结构体访问根节点二叉树的遍历前序遍历二叉树中序遍历二叉树后序遍历二叉树二叉树遍历的部分应用基于二叉树遍历输出叶子结点基于遍历序列建立二叉树基于遍历求...
- Codeplus.的博客 【数据结构——遍历二叉树和...目录【数据结构——遍历二叉树和线索二叉树】一、遍历二叉树二级目录三级目录二、线索二叉树二级目录三级目录 一、遍历二叉树 二级目录 三级目录 二、线索二叉树 二级目录 三级目录 ...
- 3年前LFuser.的博客 二叉树的层次遍历 #include&lt;stdio.h&gt; #include&lt;stdlib.h&gt; #include&lt;string.h&gt; #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 typedef struct Node{ //...
- chen.yu的博客 对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 如下就是完全二叉树 1 2 3 4 5 6 7 如下就是完全二叉树 ...