在二叉树中，查找某种遍历（如前中后序遍历、层次遍历）的前驱后继，在普通的二叉树结构中会显得很麻烦。有两种方法可以解决。
1.增加前驱后继两个指针，这样大大增加了空间消耗，不太可取。
2.将结点结构变为如下结构。若结点有左子树，left指向左孩子否则指向某种遍历的前驱。
若结点有右子树，right指向右孩子，否则指向某种遍历的后继。
这样，中序遍历的一个线索二叉树结构为：
将一个二叉树中序线索化，类似中序遍历，假如该结点有左节点，向左节点递归。
没有左节点时，对该结点进行一系列操作，再向其右节点递归。
最左下边的前驱和最右下的后继为nullptr。
考虑一个结点的前驱，两种情况。
1.前驱不是左孩子，则其left是前驱，直接返回。
2.如果是左孩子，则其前驱是其左孩子的最右下孩子的结点
后继同理。
#pragma once #include#include #include template class tbinary_tree { public: struct node { T data; node* left; node* right; bool l_mark; bool r_mark; node() = default; node(const T& d, node* const l = nullptr, node* const r = nullptr) { data = d; left = l; right = r; l_mark = false; r_mark = false; } }; node* root; tbinary_tree() :root(nullptr) {} ~tbinary_tree() { p_clear(root); } void inThread() ;//将二叉树线索化 node* last(node* current);//求前驱 node* next(node* current);//求后继 void inorder() { p_inorder(root); };//特有中序遍历 private: //名字前面有个p表示私有private void p_clear(node* root);//删除所有结点 void p_inThread(node* current, node*& pre); void p_inorder(node* root); }; template void tbinary_tree ::inThread() { node* pre = nullptr; if (root) { p_inThread(root, pre); pre->right = nullptr; pre->r_mark = true; } } template void tbinary_tree ::p_inThread(node* current, node*& pre) { if (!current) return; p_inThread(current->left, pre); if (!current->left) { current->left = pre; current->l_mark = true; } if (pre && !pre->right) { pre->right = current; pre->r_mark = true; } pre = current; p_inThread(current->right, pre); } template typename tbinary_tree ::node* tbinary_tree ::last(node* current) { node* p = current->left; if (!current->l_mark) { while (!p->r_mark) p = p->right; } return p; } template typename tbinary_tree ::node* tbinary_tree ::next(node* current) { node* p = current->right; if (!current->r_mark) { while (!p->l_mark) p = p->left; } return p; } template void tbinary_tree ::p_inorder(node* root) { //当然也可以按普通二叉树遍历,以下是线索二叉树特有的遍历 if (!root) return; node* p = root; while (p->left) p = p->left; if(p->r_mark) std::cout << p->data << " "; node* q = next(p); while (q) { std::cout << q->data << " "; q = next(q); } //另一种方式 } template void tbinary_tree ::p_clear(node* root) { if (!root)//结点为空就返回 return; node* p = root; while (p->left) p = p->left; node* q = next(p); delete p; while (q) { p = q; q = next(q); delete p; } }
