Question

如何实现二叉树的线索化

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

Answer 2

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

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

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

中序遍历线索二叉树：

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

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

后序遍历线索二叉树：

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

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