思考写在前面：
上一讲我们实现了代码量较大的二叉排序树，这一讲我们讲一个新的类型 —— 线索二叉树。这一讲代码量不多，但在理解上需要大家花一点功夫~
在我们之前学到的树中可以发现，一个拥有 N 结点的二叉树，它一定有 N-1 条边是指向节点的即有效分支，但是有 2N-(N-1) = N+1 条边是指向空指针域的，这就导致了空间上的浪费。
此外，当对二叉树进行中序遍历时可以得到二叉树的中序序列。如果所示，中序遍历的结果为 6 3 7 1 2 。但是，这种关系的获得是建立在完成遍历后得到的，那么可不可以在建立二叉树时就记录下前驱后继的关系呢，那么在后续寻找前驱结点和后继结点时将大大提升效率。
线索二叉树的定义为了利用其这些空指针域，我们将规则定义如下：
若结点的左子树为空，则该结点的左孩子指针指向其前驱结点。
若结点的右子树为空，则该结点的右孩子指针指向其后继结点。
这种指向前驱和后继的指针称为线索。将一棵普通二叉树以某种次序遍历，并添加线索的过程称为线索化。
这样构建起二叉树之后，我们可以发现，进行中序遍历的话只用从最左边的孩子开始，沿着每个结点的右指针一直遍历即可，可以不用递归了，真的不要太爽！
有些小伙伴可能已经发现了问题，这样子创建的线索树该如何区分它的左右指针呢，我怎么知道它想指向的是左右孩子还是前驱后继呀。
所以这里我们就需要在结点结构体中多定义两个变量，用于表示它左右指针的类型，并且规定如下规则：
left_type 为 0 时，指向左孩子，为 1 时指向前驱。
right_type 为 0 时，指向右孩子，为 1 时指向后继。
typedef struct Thread {
struct Thread* left_node; //左指针
struct Thread* right_node; //右指针
int data;
//默认0代表左右孩子，1代表前驱或者后继
int left_type; //左指针类型
int right_type; //右指针类型
}Node;
通过上述变换之后，就得到了这样的一颗线索二叉树：
我们可以通过中序遍历的方式进行构建，这里需要一个指向前驱结点的指针和一个指向当前结点的指针。遍历的方式跟我们之前学的二叉树的中序遍历几乎一样，先来回顾一下二叉树的遍历：
//中序遍历
void show_tree(tree_node *node) {
if (node == NULL)
return;
show_tree(node->left_child);
cout << node->data << " ";
show_tree(node->right_child);
}
这里构建线索二叉树时，只需要改动上面代码中打印结点的那一部分，将那里改成对前驱后继连接的代码即可。
Node* pre = NULL; //前驱结点的变量
Node* head; //头指针
//中序线索化
void inOrderThreadTree(Node* node)
{
if (node == NULL)
{
return;
}
inOrderThreadTree(node->left_node); //先遍历到最左边
if (node->left_node == NULL)
{
//设置前驱结点
node->left_type = 1;
node->left_node = pre;
}
//如果结点的右子结点为NULL，则处理前驱的右指针
if (pre != NULL && pre->right_node == NULL)
{
//设置后继
pre->right_node = node;
pre->right_type = 1;
}
pre = node; //更新前驱指针
inOrderThreadTree(node->right_node); //在遍历右边孩子
}
线索二叉树的遍历
当构建其线索二叉树之后，我们每次遍历它就变得十分方便，不用不断的递归了，直接找到最左边的那个结点（中序遍历第一个打印的是最左边的孩子），然后沿着右指针一条路走到黑，不断输出即可。
//中序遍历
void inOrderTraverse(Node* root)
{
//从根结点开始找到最左边
if (root == NULL)
{
return;
}
Node* temp = root;
while (temp != NULL && temp->left_type == 0)
{
temp = temp->left_node; //找到最左边的结点
}
//开始打印结点
while (temp != NULL)
{
cout << temp->data << " ";
temp = temp->right_node;
}
}
全部代码
#includeusing namespace std; typedef struct Thread { struct Thread* left_node; //左指针 struct Thread* right_node; //右指针 int data; //默认0代表左右孩子，1代表前驱或者后继 int left_type; //左指针类型 int right_type; //右指针类型 }Node; Node* pre = NULL; //前驱结点的变量 Node* head; //头指针 //中序线索化 void inOrderThreadTree(Node* node) { if (node == NULL) { return; } inOrderThreadTree(node->left_node); //先遍历到最左边 if (node->left_node == NULL) { //设置前驱结点 node->left_type = 1; node->left_node = pre; } //如果结点的右子结点为NULL，则处理前驱的右指针 if (pre != NULL && pre->right_node == NULL) { //设置后继 pre->right_node = node; pre->right_type = 1; } pre = node; //更新前驱指针 inOrderThreadTree(node->right_node); //在遍历右边孩子 } //中序遍历 void inOrderTraverse(Node* root) { //从根结点开始找到最左边 if (root == NULL) { return; } Node* temp = root; while (temp != NULL && temp->left_type == 0) { temp = temp->left_node; //找到最左边的结点 } //开始打印结点 while (temp != NULL) { cout << temp->data << " "; temp = temp->right_node; } }
如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~
【上一讲】树 - 03 二叉排序树
