前言
最近在读霍罗维兹的《数据结构基础》（Fundamentals of Data Structures in C），本篇博客为阅读笔记和知识总结。
0x00 线索（threads）
具有 个结点的二叉链表共有
个链域，其中
为空链域。
A.J.Perlis 与 C.Thornton 提出一种方法，用用原来的空链域存放指针，指向树中的其他结点。
这种指针就被称为 线索（threads），记 ptr 指向二叉链表中的一个结点，一下是建线索的规则：
① 如果 ptr->leftChild 为空，则存放指向中序遍历排列中该节点的前驱结点。该节点成为 ptr 的?中序前驱（inorder predecessor）。
② 如果 ptr->rightChild 为空，则存放指向中序遍历序列中该结点的后继节点。这个节点称为 ptr 的中序后继（inorder successor）。
当我们在内存中表示树时，我们必须能够区分线程和普通指针。
这是通过在节点结构中添加两个额外的字段来实现的，即 left_thread 和 right_thread 。
typedef struct threaded_tree* threaded_pointer;
typedef struct threaded_tree {
short int left_thread;
threaded_pointer left_child;
char data;
threaded_pointer right_child;
short int right_thread;
};?我们假设所有线程二叉树都有一个头结点。
线程二叉树的无序遍历 确定一个节点的无序继承者。
[Program 5.10]??Finding the inorder successor of a node.
threaded_pointer insucc(threaded_pointer tree)
{
/* find the inorder successor of tree
in a threaded binary tree */
threaded_pointer temp;
temp = tree->right_child;
if (!tree->right_thread)
while (!temp->left_thread)
temp = temp->left_child;
return temp;
}为了进行中序遍历，我们反复调用 insucc?
[Program 5.11]? Inorder traversal of a threaded binary tree.
void tinorder(threaded_pointer tree)
{
/* traverse the threaded binary tree inorder */
threaded_pointer temp = tree;
for (; ; ) {
temp = insucc(temp);
if (temp == tree) break;
printf("%3c", temp->data);
}
}向线程二叉树插入一个节点，假设我们有一个节点，即 parent，它的右子树是空的。我们希望插入child 作为父节点的右子节点。
要做到这一点，我们必须：
① 将 parent-> right_thread 改为 FALSE
② 将 child->left_thread 和 child->right_thread 改为 TRUE
③ 将 child->left_child 改为指向 parent
④ 将 child->right_child 改为 parent->right_child
⑤ 将 parent->right_child 改为指向 child?
对于 parent 具有非空右子树的情况：
处理这两种情况的 C 代码如下：
[Program 5.12] : Right insertion in a threaded binary tree
void insert_right(threaded_pointer parent, threaded_pointer child) {
/* insert child as the right child of parent in a threaded binary tree */
threaded_pointer temp;
child->right_child = parent->right_child;
child->right_thread = parent->right_thread;
child->left_child = parent;
child->left_thread = TRUE;
parent->right_child = child;
parent->right_thread = FALSE;
if (!child->right_thread) {
temp = insucc(child);
temp->left_child = child;
}
}参考资料
Fundamentals of Data Structures in C
