如何实现二叉树的线索化

线索化二叉树虚线是怎么画的？~

虚线即为线索，是原来没有孩子时的空指针改为指向遍历序列的前驱后继，其中左边链指向遍历序列前驱，右边链指向遍历序列的后继。
在二叉树的结点上加上线索的二叉树称为线索二叉树，对二叉树以某种遍历方式（如先序、中序、后序或层次等）进行遍历，使其变为线索二叉树的过程称为对二叉树进行线索化。
对于n个结点的二叉树，在二叉链存储结构中有n+1个空链域，利用这些空链域存放在某种遍历次序下该结点的前驱结点和后继结点的指针，这些指针称为线索，加上线索的二叉树称为线索二叉树。
这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

扩展资料
建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。
为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。
另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。
参考资料来源：百度百科-线索二叉树

线索二叉树就是
使用的对象：树节点中没有使用的n-1个空指针（n个树节点，空指针永远都是n+1个，自己推下）。
运行的原则：某种深度遍历顺序——先序，中序，后序
过程：按照中序（当然也可以是其他的遍历）的前驱后继关系，若p的左子树为空，则左子树指向p的中序前驱，若p的右子树为空，则p的右子树节点指向p的后继，若是子树都有，就不用捣腾了。第一个节点的左子树为空（此节点一定是叶节点，而且没前驱，所以是空），最后一个节点的右子树也是空。
数据结构：在树节点的结构是（data，*lchild，*rchild）线索树的节点是（data，*lchild，*rchild，ltag，rtag），tag为1表示线索数的节点，为0标识树节点。
目的：方便找到树在某种遍历的条件下前驱和后继。不是用来遍历的哈
注意的点：只用中序线索树可以很完美的达到这个效果，前序线索树在计算前驱的时候会牵扯到自己的父节点，就要使用栈来找，这样和遍历查找没区别，同理，后序线索树找后继会比较麻烦。

话说，要点基本就这样了。
细节的点，比如说为什么n+1啊，为什么前序后序不完美啊，这些一边就考个知道，而且推理是很快的，所以呢，考试的话，就照着我说的这几个点就ok了，主要是要会画，还有就是中序查找的实现。
中序实现给你一个要点：
找前驱：向左找第一个rtag为1的就是它的前驱了。
因为在中序中，所有的内节点（非叶节点）的前驱和后继必然是一个叶节点。
要是记不住算法，记住这点临场写也够了，前提是老兄您在之前弄明白我的要点的意义。

1. 先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。
   

2. 先序遍历线索二叉树：
   

3. 首先进行先序遍历，然后把得到的节点依次入队；
   

4. 然后把队列里除了根节点以外的节点依次根据标记，队里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。
   

5. 中序遍历线索二叉树：
   

6. 首先进行中序遍历，然后把得到的节点依次入队
   

7. 然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。
   

8. 后序遍历线索二叉树：
   

9. 首先进行后序遍历，然后把得到的节点依次入队
   

10. 然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1。

11. 树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。

12. 树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。满二叉树，完全二叉树，排序二叉树。

自己理解得方法：
先把二叉树给标记化：既设置两个标记Ltag，Rtag，如果左孩子指针为空，Ltag=1，如果右孩子指针为空，Rtag=1。

先序遍历线索二叉树：
首先进行先序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

中序遍历线索二叉树：

首先进行中序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，右指针指向队里后一个元素。

后序遍历线索二叉树：

首先进行后序遍历，然后把得到的节点依次入队

然后把队列里除了根节点以外的节点依次根据标记，队列里首节点Ltag=0，如果Ltag=1，左指针指向队里前一个元素，如果Rtag=1，

---

济源市17839169401： c语言怎么利用 顺序或链式结构实现中序线索化二叉树?? - ？
励琦加巴： 线索化二叉树实质就是将二叉树中的空指针改成指向前驱后者后继的指针 从而确定二叉树的唯一性 而前驱后后继只能在遍历中才能确定 所以要对二叉树进行中序遍历的过程中进行线索化 中序线索化二叉树源码 #include ＂stdio.h＂#include ＂...

济源市17839169401： 数据结构线索化二叉树 - ？
励琦加巴： 1、T为二叉树的根结点2、pre指针初始化,让其指向线索二叉树的头结点,作用是使得对二叉树的最“左”结点的处理与对其它结点的线索化处理的方法一致.3、是这样的,对p结点的左子树进行线索化4、如果当前结点(即p指向的结点)没有左孩子,那么让左孩子指针指向pre所指的结点.5、让pre指向当前结点,那么它不就是下一个结点的前趋结点了嘛6、综上pre指针始终指向p所指向的当前结点前趋结点.总体上使用的递归思想,即对整颗树先对其左子树遍历,然后对当前结点线索化,最后对右子树递归遍历.

济源市17839169401： 二叉树线索化 - ？
励琦加巴： struct lrtree; typedef struct{int vallrtree *left;lrtree *right; }lrtree;#define MAX_STACK 1000 lrtree *pstack[MAX_STACK]; int pn = 0;void pushtree(lrtree *p) {if pn < MAX_STACK{pstack[pn++] = p;}else{printf(＂stack overfilled!＂);} } lrtree ...

济源市17839169401： 有人愿意画张图帮我理解下二叉树线索化算法吗 - ？
励琦加巴： 前后两个递归就是利用中序遍历来线索化 中间的等于是访问根结点: 如果没有左孩子,就要将左指针线索化指向中序刚刚访问过的前驱pre 如果前驱没有右孩子,就要将其右指针线索化指向当前结点(也就是前驱的后继) 最后pre指向当前访问的结点

济源市17839169401： 如何给已创建的二叉树前序添加线索(C++),请高手指点!谢谢~ - ？
励琦加巴： //前序线索化以t为根的二叉树 void ThreadTree::ThreadingPre(ThreadNode * t) { if(t==NULL) return; //处理当前结点 if(t->GetLeft()==NULL) { t->SetLThread(1); t->SetLeft(pre); } else t->SetLThread(0); if(t->GetRight()==NULL) { t->SetRThread(1); t->...

济源市17839169401： 在实现线索化二叉树时如何找到结点的前驱与后继 - ？
励琦加巴： 先把二叉树给标记化(把二叉树遍历一遍):既设置两个标记Ltag,Rtag,如果左孩子指针为空,Ltag=1,如果右孩子指针为空,Rtag=1. 建一个队列,根据你的遍历方式进行入队, 比如先序遍历,就把visit到的元素依次入队,特别注意,中序遍历或后序遍历visit是从左下角开始的,不是根节点,如果还是不懂,就把输出元素那行改成入队的代码就ok了 然后如果Ltag=1,此时把左孩子指针回指队里前一个元素,这个元素就是前驱节点,然后往队尾依次进行线索化,同理,后继的话为Rtag=1时,你也应该知道怎么弄了吧.

济源市17839169401： 求教,如何将此普通二叉树转换成线索二叉树 - ？
励琦加巴： 树转二叉树是这样的:对于一个节点,他的左儿子是他的某个儿子(若他原来就没有儿子就没有左儿子) 他的右儿子是他的某个兄弟

济源市17839169401： 中序二叉树线索化 - ？
励琦加巴： InThreaded(curr->Left(),pre); //这句 ,结点往左走,pre还不变吗?还能这样写吗? 这个是递归调用本函数,如果不为空,有节点,就顺左子树的线路往下找,pre指向该节点本身的前驱节点(也就是左孩子)if(pre==NULL) curr->Lth()=1; //置...

济源市17839169401： 线索二叉树的实现 数据结构 - ？
励琦加巴： 参考一下这个吧...#include <stdio.h>#include <stdlib.h>#define OK 1#define NULL 0 typedef int Status; typedef char TElemType; typedef struct BiTNode //二叉树的二叉链表存储表示 {TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *...

济源市17839169401： 二叉树线索化的思想是什么? - ？
励琦加巴： 线索二叉树就是 使用的对象:树节点中没有使用的n-1个空指针(n个树节点,空指针永远都是n+1个,自己推下). 运行的原则:某种深度遍历顺序——先序,中序,后序 过程:按照中序(当然也可以是其他的遍历)的前驱后继关系,若p的左...