当前位置：首页 > backend >正文

线索二叉树

backend 2025/5/9 7:00:38

一概念

线索二叉树（Threaded Binary Tree）是一种对二叉树的优化结构，主要解决传统二叉树遍历时需要借助栈或递归（额外空间开销）的问题。通过利用节点中的空指针（nullptr）存储遍历过程中的前驱或后继节点信息（称为 “线索”），可以实现无需额外空间的二叉树遍历。

传统二叉树中，每个节点有两个指针（左孩子lchild、右孩子rchild）。对于一棵有n个节点的二叉树，共有2n个指针域，但其中只有n-1个指针被有效使用（连接子节点），剩余n+1个指针为空（nullptr）。
线索二叉树的核心思想是：将这些空指针利用起来，存储节点在某种遍历顺序（如中序、前序、后序）中的前驱或后继节点的地址，这些被重新利用的指针称为 “线索”。

为了区分一个指针是指向子节点还是线索，每个节点需要增加两个标志位：

ltag：左标志位
- ltag = 0：lchild指向左子节点
- ltag = 1：lchild是前驱线索（指向当前节点在遍历顺序中的前驱）
rtag：右标志位
- rtag = 0：rchild指向右子节点
- rtag = 1：rchild是后继线索（指向当前节点在遍历顺序中的后继）

二代码

1.线索二叉树结点

//线索二叉树结点
struct TreeNode {int data;TreeNode* left;TreeNode* right;bool ltag; //左线索，若为true,则left表示前驱结点，否则为左孩子结点bool rtag; //右线索，若为true,则right表示前驱结点，否则为右孩子结点TreeNode(int d) : data(d), left(nullptr), right(nullptr), ltag(false), rtag(false) {}
};

新增左右线索标志。若左线索为true，则left表示前驱结点，否则为左孩子结点。若右线索为true，则right表示后继结点，否则为右孩子结点。

2.构建线索二叉树

//构建线索二叉树(通过前序遍历序列构建)
TreeNode* CreateTree(vector<int>& preorder, int& index, int nullnode) {//若索引超出数组范围或数组索引处为空值nullnode,则令index++并返回空if (index >= preorder.size() || preorder[index] == nullnode) {index++;return nullptr;}TreeNode* node = new TreeNode(preorder[index++]); //为新结点分配内存node->left = CreateTree(preorder, index, nullnode); //递归构建左子树node->right = CreateTree(preorder, index, nullnode); //递归构建右子树return node; //返回当前结点
}

通过前序遍历序列来构建线索二叉树，若传入的索引超出数组范围或数组索引处为空值nullnode，则令Index++并返回空。为新结点分配内存，然后递归构建左右子树。

3.中序遍历线索化

//中序遍历线索化
TreeNode* pre = nullptr; //定义前驱结点void inorderThreading(TreeNode* node) {if (node == nullptr) return; //当传入结点为空时直接返回inorderThreading(node->left); //递归左子树，找到最左边孩子结点//传入结点的左子结点为空时，令其左指针指向前驱结点preif (node->left == nullptr) { node->left = pre;node->ltag = true;}//当前驱结点不为空且其右子结点为空时，令前驱结点的右指针指向当前结点if (pre && pre->right == nullptr) { pre->right = node;pre->rtag = true;}pre = node; //令前驱结点指向当前结点inorderThreading(node->right); //递归右子树
}

中序遍历线索化是最常用的线索化方式。首先在函数外定义一个全局结点变量pre表示前驱结点。

在函数体中，当传入的结点为空时直接返回。先递归左子树找到最左边孩子结点，当传入结点的左子结点为空时，令其左指针指向前驱结点pre，当前驱结点不为空且右子结点为空时，令前驱结点的右指针指向当前结点。最后令前驱结点指向当前结点并递归右子树。

4.中序遍历线索二叉树

//中序遍历线索二叉树
void inorderTraversal(TreeNode* root) {TreeNode* p = root;//找到中序遍历第一个节点（最左叶子）while (!p->ltag) { // 左线索为false表示有左子树，继续往左找p = p->left;}//循环遍历所有节点while (p != nullptr) {cout << p->data; //访问当前结点//找后继结点if (p->rtag) { //若rtag为true,则直接通过右线索找到后继结点p = p->right;}else { //若rtag为false,则找右子树的最左子结点p = p->right;while (!p->ltag) {p = p->left;}}}
}

首先找到中序遍历的第一个结点（最左叶子结点），左线索为false表示有左子树，继续往左找。

找到后循环遍历所有结点，每次循环先访问当前结点，然后找后继结点。若rtag为true，则直接通过右线索找到后继结点，若rtag为false，则找右子树的最左子结点。

5.释放内存

//释放线索二叉树内存
void FreeTree(TreeNode* root) {if (root == nullptr) return; // 空树直接返回// 保存当前节点的左右真实子节点（仅当标志为false时有效）TreeNode* leftChild = (root->ltag == false) ? root->left : nullptr;TreeNode* rightChild = (root->rtag == false) ? root->right : nullptr;// 递归释放左右子树（仅处理真实子节点）FreeTree(leftChild);FreeTree(rightChild);//释放当前结点delete root;root = nullptr; //指向空，避免野指针
}

若传入结点为空，直接返回。保存当前结点的左右真实结点，仅当标志为false时有效。接着递归释放左右子树，仅处理真实子结点。然后释放当前结点并让当前结点指向空以避免野指针。