一. 线索二叉树的创建、遍历
运行结果
代码如下，注释为王
#include<iostream>
// 线索二叉树结点定义
typedef struct TBTNode {
int data; // 值域
int ltag, rtag; // 左右线索标记
struct TBTNode* lchild; // 左指针
struct TBTNode* rchild; // 右指针
// 默认构造
TBTNode() :data(0), ltag(0), rtag(0), lchild(0), rchild(0) {}
// 带参构造
TBTNode(int _data) :data(_data), ltag(0), rtag(0) {
this->lchild = this->rchild = 0;
}
} TBTNode;
// 二叉排序树的插入
int BSTInsert(TBTNode*& bt, int key) {
if (bt == 0) {
bt = new TBTNode;
bt->lchild = bt->rchild = 0;
bt->data = key;
return 1; // 插入成功标志
}
else {
if (key == bt->data) return 0; // 插入失败返回 0
else if (key < bt->data)
return BSTInsert(bt->lchild, key); // 关键字小于根结点值，作为左孩子插入
else
return BSTInsert(bt->rchild, key); // 关键字大于根结点值，作为右孩子插入
}
}
// 构造二叉排序树
void CreateBST(TBTNode*& bt, int key[], int n) {
bt = 0; // 将树清空
for (int i = 0; i < n; ++i) {
BSTInsert(bt, key[i]); // 依次将每个关键字插入到二叉排序树中
}
}
// 中序遍历对二叉树线索化的递归算法
void InThread(TBTNode* p, TBTNode*& pre) { // p 为当前正在访问的结点，pre 指向 p 的前驱结点
if (p != 0) {
InThread(p->lchild, pre); // 递归，左子树线索化
if (p->lchild == 0) { // p 没有左孩子，建立当前结点的前驱线索
p->lchild = pre; // 则为线索指向它的前驱
p->ltag = 1; // 标记改为 1， 表明为线索
}
if (pre != 0 && pre->rchild == 0) { // pre 的右线索如果存在
pre->rchild = p; // 则让它指向 p，因为 p 是 pre 的后继结点，建立当前结点的后继线索
pre->rtag = 1; // 标记改为 1， 表明为线索
}
pre = p; // pre 指向当前的 p，作为 p 将要指向的下一个结点的前驱结点的指示指针
InThread(p->rchild, pre); // 递归，右子树线索化
}
}
// 中序遍历建立线索二叉树
void createInThread(TBTNode* root) {
TBTNode* pre = 0; // 前驱节点指针
if (root != 0) {
InThread(root, pre); // 中序线索化
pre->rchild = 0; // 非空二叉树，线索化后处理中序最后一个结点
pre->rtag = 1; // 将最后一个结点的指针域指向空并标记为线索
}
}
// 中序递归遍历 （LNR）
void inOrder(TBTNode* p) {
if (!p) return;
inOrder(p->lchild);
std::cout << p->data << '\t';
inOrder(p->rchild);
}
// 以 p 为根的中序线索二叉树中，中序下的第一个结点
TBTNode* First(TBTNode* p) {
while (p->ltag == 0) p = p->lchild; // 最左下角的结点（不一定是叶结点，可能该结点还有右子树）
return p;
}
// 中序线索二叉树中 q 在中序下的后继节点
TBTNode* Next(TBTNode* q) {
if (q->rtag == 0) return First(q->rchild); // 有右子树则返回右子树最左下角的结点
else return q->rchild; // rtag == 1，直接返回后继线索
}
// 遍历中序线索二叉树
void Inorder(TBTNode* root) {
// 就像打印线性表一样打印线索二叉树，for/while 实现如下
//for (auto p = First(root); p != 0; p = Next(p)) {
// std::cout << p->data << '\t'; // 打印结点值
//}
auto p = First(root);
while (p != nullptr) {
std::cout << p->data << '\t';
p = Next(p);
}
std::cout << std::endl;
}
int main() {
int key[]{ 5,2,6,8,7,9,3 }; // 测试数组
std::cout << "打印测试数组：\n";
for (auto& i : key) {
std::cout << i << '\t';
}
std::cout << '\n';
TBTNode* root = new TBTNode; // 生成根结点
CreateBST(root, key, sizeof(key) / sizeof(key[0])); // 构造二叉排序树
std::cout << "递归中序遍历二叉排序树应为递增序列：\n";
inOrder(root);
std::cout << '\n';
createInThread(root);
// 遍历线索二叉树
std::cout << "遍历线索二叉排序树也应为递增序列：\n";
Inorder(root);
system("pause");
return 0;
}
二. 前、后序递归线索化二叉树（补充）
都和中序线索化代码极为相似
// 前序遍历对二叉树线索化的递归算法
void preThread(TBTNode* p, TBTNode*& pre) { // p 为当前正在访问的结点，pre 指向 p 的前驱结点
if (p != 0) {
if (p->lchild == 0) { // p 没有左孩子，建立当前结点的前驱线索
p->lchild = pre; // 则为线索指向它的前驱
p->ltag = 1; // 标记改为 1， 表明为线索
}
if (pre != 0 && pre->rchild == 0) { // pre 的右线索如果存在
pre->rchild = p; // 则让它指向 p，因为 p 是 pre 的后继结点，建立当前结点的后继线索
pre->rtag = 1; // 标记改为 1， 表明为线索
}
pre = p; // pre 指向当前的 p，作为 p 将要指向的下一个结点的前驱结点的指示指针
// 注意！这里递归条件入口有限制，左、右指针不是线索才能继续递归
if(p->ltag == 0) preThread(p->lchild, pre); // 有左子树（左指针），左子树线索化
if(p->rtag == 0) preThread(p->rchild, pre); // 有右子树（右指针），右子树线索化
}
}
// 后序遍历对二叉树线索化的递归算法
void postThread(TBTNode* p, TBTNode*& pre) { // p 为当前正在访问的结点，pre 指向 p 的前驱结点
if (p != 0) {
// 注意！左右递归入口都放到了前边
postThread(p->lchild, pre); // 递归，左子树线索化
postThread(p->rchild, pre); // 递归，右子树线索化
if (p->lchild == 0) { // p 没有左孩子，建立当前结点的前驱线索
p->lchild = pre; // 则为线索指向它的前驱
p->ltag = 1; // 标记改为 1， 表明为线索
}
if (pre != 0 && pre->rchild == 0) { // pre 的右线索如果存在
pre->rchild = p; // 则让它指向 p，因为 p 是 pre 的后继结点，建立当前结点的后继线索
pre->rtag = 1; // 标记改为 1， 表明为线索
}
pre = p; // pre 指向当前的 p，作为 p 将要指向的下一个结点的前驱结点的指示指针
}
}