如果一棵二叉树，所有原本为空的右孩子改为指向该结点的中序遍历的后继，所有原本为空的左孩子改为指向该结点的中序遍历的前驱，那么修改后的二叉树被称为 线索二叉树 (Threaded binary tree, TBT)。指向前驱、后继的指针被称为线索，对二叉树以某种遍历顺序进行扫描并为每个结点添加线索的过程称为二叉树的 线索化 ，进行线索化的目的是为了加快查找二叉树中某节点的前驱和后继的速度。
TBT 能线性地遍历二叉树，从而比递归的中序遍历更快。使用 TBT 也能够方便的找到一个结点的父结点，这比显式地使用父结点指针或者栈效率更高。这在栈空间有限，或者无法使用存储父节点的栈时很有作用。
TBT 的存储结构
如果一棵二叉树线索化之后，需要分辨哪些是线索哪些是边，因此我们不得不修改数据结构，使得有 field 来指示该结点的左或右孩子是否是线索。
该节剩下内容将作为扩展部分，可以进行选择性阅览。
我们改写为代码，由于 tag 实际上至于要 1 bit 就能指示线索，这时候 C / C++ 的优势就体现出来了，我们可以通过 位域 限制 tag 的大小，并将两个 tag 合并在 1 Byte 上来减少结构体空洞带来的内存浪费。
// 假设运行在 UNIX-like 64 bit OS 之上 template <class Element> struct ThreadedBinaryTreeNode { Element data; // 占用 ?? byte // 产生 ?? bit 空洞 int ltag : 1; int rtag : 1; // 产生 62 bit 空洞 ThreadedBinaryTreeNode* left; // 占用 8 byte // 如果 rtag 在这里定义，数据结构大小将增加 8 byte，其中包含 63 bit 的空洞 ThreadedBinaryTreeNode* right; // 占用 8 byte };
在之前的内容中，所有代码尽量都避免 C / C++ 的一些深度的语言特性，来避免读者因为编程语言的特性而带来的困扰。但是下面这个例子，将展示 C / C++ 因为其底层、灵活而展示出的强大。
在 LP64 模型下指针大小为 64 bit，从堆上分配来的内存的地址，起始地址能够被其最宽的成员大小整除。那么含有指针的 TreadedBinaryTreeNode 在分配时其地址可以被 8 byte 整除，这是什么概念的，就是其地址的 低 3 bit 一定为 0 。我们可以充分利用这 3 bit，在不改变二叉树结点结构的情况下，辨别该结点是否是线索。如此整个结构体大小缩小了 8 byte。其实这个技巧在很多 C 代码中都有使用，甚至你可以考虑将结构体空洞废物利用起来，或者 C 的宏编程，这些 奇技淫巧 威力强大但降低了代码的可读性。
使用最低 3 bit 存储状态，那么我们在使用时就不能直接使用指针了，那么下列函数可能会对你使用这 3 bit 有帮助。
enum NodeStatus { LINK, THREAD, }; constexpr uintptr_t HIDE_BIT = 3; inline BinaryTreeBaseNode* get_node(BinaryTreeBaseNode* node) { return reinterpret_cast<BinaryTreeBaseNode*>(reinterpret_cast<uintptr_t>(node) & ~HIDE_BIT); } inline BinaryTreeBaseNode* get_left(BinaryTreeBaseNode* node) { return get_node(get_node(node)->left); } inline BinaryTreeBaseNode* get_right(BinaryTreeBaseNode* node) { return get_node(get_node(node)->right); } inline int get_status(BinaryTreeBaseNode* node) { return reinterpret_cast<uintptr_t>(node) & HIDE_BIT; } inline void set_left_link(BinaryTreeBaseNode* node, BinaryTreeBaseNode* left) { node->left = left; } inline void set_left_thread(BinaryTreeBaseNode* node, BinaryTreeBaseNode* left) { node->left = reinterpret_cast<BinaryTreeBaseNode*>(reinterpret_cast<uintptr_t>(left) | NodeStatus::THREAD); } inline void set_right_link(BinaryTreeBaseNode* node, BinaryTreeBaseNode* right) { node->right = right; } inline void set_right_thread(BinaryTreeBaseNode* node, BinaryTreeBaseNode* right) { node->right = reinterpret_cast<BinaryTreeBaseNode*>(reinterpret_cast<uintptr_t>(right) | NodeStatus::THREAD); } inline bool is_thread(BinaryTreeBaseNode* node) { return get_status(node) == NodeStatus::THREAD; }
线索化
线索化时需要记录结点的前驱，如果你仔细观察 Morris Traversal，你可能会发现， Morris Traversal 是在构建一部分线索二叉树。
template <class Element> void inorder_threading(ThreadedBinaryTreeNode<Element>* root) { auto curr = root, prev = root; while (curr != nullptr) { if (curr->left == nullptr) { curr->left = prev; curr->ltag = NodeStatus::THREAD; prev = curr; goto RIGHTING; } prev = curr->left; while (prev->right != nullptr && prev->right != curr) { prev = prev->right; } if (prev->right == nullptr) { prev->right = curr; prev->rtag = NodeStatus::THREAD; curr = curr->left; continue; } prev = prev->right; RIGHTING: curr = curr->right; } // 由于 root 的后继的左线索指向不正确，需要对其进行修正 if (root->right != nullptr) { curr = root->right; while (curr->ltag == NodeStatus::LINK) { curr = curr->left; } curr->left = root; curr->ltag = NodeStatus::THREAD; } // 由于中序遍历第一个结点的左线索指向不正确，将其置空。其最后一个结点同样也是置空的 curr = root; while (curr->ltag == NodeStatus::LINK) { curr = curr->left; } curr->left = nullptr; curr->ltag = NodeStatus::LINK; }
