【数据结构算法】12-线索⼆叉树
父亲的眼泪⽬录
前⾔
在《⼤话数据结构》P190 页中有⼀句话：其实线索⼆叉树，就等于是把⼀棵⼆叉树转变成了⼀个双向链表。
对于这句话实在想不懂，线索⼆叉树只是把⼆叉树以某种次序遍历把空域填上前驱或后继⽽已，若度为 2 的结点没有多余的指针域⽤于线索了，那双向链表就断了啊。线索⼆叉树的概念
概念：
引⼊原因：⼆叉链表中，只能看出左右孩⼦，⽽看不出某序遍历的前驱和后继。
线索：指向前驱和后继的指针称为线索。
线索链表：加上线索的⼆叉链表称为线索链表。
线索⼆叉树（Threaded Binary Tree）：加上线索的⼆叉树称为线索⼆叉树。
左域为空则改为前驱。
右域为空则改为后继。
每个节点添加左右 tag，⽤于标记左右域指针是孩⼦还是线索。
线索化：对⼆叉树以某种次序遍历使其变为线索⼆叉树的过程。
甲的组词前、中、后序线索⼆叉树。
线索⼆叉树的实现
前驱和后继的信息只有在遍历⼆叉树时才能得到。⽽在遍历⼆叉树时便可以线索化。
线索化：
在遍历过程中修改空指针。
空左域为前驱。
空右域为后继。
手机号码实名查询
实际实现：
前、中、后序：正常的中序遍历算法。在遍历过程中，把输出数据部分改为线索化内容，即是修改空指针。
线索⼆叉树的遍历：
中序：采⽤⾮递归⽅式：
中序遍历算法思路：先找到最左下，再中，再切到右⼦树找到右⼦树的最左下，再中，再右...。
简单来说就是：左、中、右。先找最左下。切到右时也要先找右的最左下。
实现步骤：
找最左下：⼀直循环找左孩⼦，直到找到 ltag 为线索的节点。
找到最左下节点后，输出数据。
判断该节点是否有后继。
有：则直接跳到后继节点。输出数据。判断该节点是否有后继（就是重复步骤 3）。（线索）
⽆：则切到右孩⼦，对该右⼦树做前序遍历。即是找这个右孩⼦的最左下（重复步骤 1 、2、3）。（孩⼦）
提醒：左右域只有两种情况：1. 线索；2. 孩⼦。
线索⼆叉树节点：
/* 线索⼆叉树节点结构 */
typedef int tree_elem_type;
/* link_e==0表⽰指向左右孩⼦指针, */
/* thread_e==1表⽰指向前驱或后继的线索 */
typedef enum {link_e, thread_e} pointer_tag_e;
不成比例
typedef struct tree_node
{
struct tree_node *lchild; // 左⼦域
struct tree_node *rchild; // 右兄域
苹车
pointer_tag_e ltag; // 左标志
pointer_tag_e rtag; // 右标志
tree_elem_type data; // 数据
}binary_tree_node_t;
线索化代码参考下⾯参考代码。
线索⼆叉树的寻点思路⼆
以中序线索⼆叉树为例，令 P 所指节点的某个结点。查找 p 所指结点的后继点的⽅法：
若 p->rtag==1，则 p->rchild 指向其后继节。
若 p->rtag==0，则 p 所指结点的中序后继必然是其右⼦树中进⾏中序遍历时得到的第⼀个结点。也就是 p 的右⼦树中“最左下”的结点。
这点可以利⽤递归。
也可以参考下⾯代码的⾮递归⽅法。平方米和平方千米
寻点代码参考下⾯代码。
类双向链表参考图
怎么改qq密码参考代码
中序遍历线索化
注意：in_threading(); 函数使⽤前需要对 pre 节点进⾏赋有效节点值。
下⾯为类双向链表线索化和线索遍历参考代码
binary_tree_node_t *pre = NULL; /* 全局变量, 上⼀访问节点 */
/* 中序遍历进⾏中序线索化 */
void in_threading(binary_tree_node_t *p)
{
if(p)
{
in_threading(p->lchild); /* 递归左⼦树线索化 */
if(!p->lchild) /* 没有左孩⼦ */
{
猫吃火腿肠p->ltag = thread_e; /* 前驱线索 */
p->lchild = pre; /* 左孩⼦指针指向前驱 */
}
if(!pre->rchild) /* 前驱没有右孩⼦ */
{
pre->rtag = thread_e; /* 后继线索 */
pre->rchild = p; /* 前驱右孩⼦指针指向后继(当前结点p) */
}
pre = p; /* 保持pre指向p的前驱 */
in_threading(p->rchild); /* 递归右⼦树线索化 */
}
}
/* 中序遍历⼆叉树tree，并将其中序线索化,tree_list指向头结点 */
int in_order_threading(binary_tree_node_t **tree_list_p, binary_tree_node_t *tree) {
*tree_list_p = (binary_tree_node_t *)malloc(sizeof(binary_tree_node_t));
if(!*tree_list_p)
return -1;
(*tree_list_p)->ltag = link_e; /* 孩⼦，⽤于指根 */
(*tree_list_p)->rtag = thread_e; /* 线索，只最右下。即是链尾 */
(*tree_list_p)->rchild = (*tree_list_p); /* 初始化：右指针回指 */
if(!tree) /* 若⼆叉树空，则左指针回指 */
(*tree_list_p)->lchild = *tree_list_p;
el
{
(*tree_list_p)->lchild = tree;
pre = (*tree_list_p);
in_threading(tree); /* 中序遍历进⾏中序线索化 */
pre->rchild = *tree_list_p;
pre->rtag = thread_e; /* 最后⼀个结点线索化 */
(*tree_list_p)->rchild = pre;
}
return 0;
}
/* 中序遍历⼆叉线索树tree(头结点)的⾮递归算法 */
int in_order_traver_tree_list(binary_tree_node_t *tree)
{
binary_tree_node_t *p = NULL;
p = tree->lchild; /* p指向根结点 */
while(p != tree)
{
/* 找到最左下节点 */
while(p->ltag == link_e)
p = p->lchild;
if(!visit(p->data)) /* 访问其左⼦树为空的结点 */
return -1;
/* 判断是否有后继，且不是整个树的最右下节点 */
while(p->rtag == thread_e && p->rchild != tree)
{
p = p->rchild;
visit(p->data); /* 访问后继结点 */
}
p = p->rchild; /* 切换到右⼦树。然后继续中序遍历该右⼦树 */ }
return -1;
}
