#include <iostream>
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
bool leftThread; // 标识左子树是否为线索
bool rightThread; // 标识右子树是否为线索
TreeNode(int value) : val(value), left(nullptr), right(nullptr), leftThread(false), rightThread(false) {}
};
// 中序线索化二叉树
void InorderThread(TreeNode* root, TreeNode*& prev) {
if (root == nullptr) {
return;
}
// 线索化左子树
InorderThread(root->left, prev);
// 处理当前节点
if (root->left == nullptr) {
root->left = prev;
root->leftThread = true;
}
if (prev != nullptr && prev->right == nullptr) {
prev->right = root;
prev->rightThread = true;
}
prev = root;
// 线索化右子树
InorderThread(root->right, prev);
}
// 中序线索化遍历二叉树
void InorderThreadTraversal(TreeNode* root) {
TreeNode* node = root;
while (node != nullptr) {
// 找到中序遍历的第一个节点,即最左下的节点
while (node->left != nullptr && !node->leftThread) {
node = node->left;
}
std::cout << node->val << " ";
// 判断右指针类型
if (node->rightThread) {
node = node->right;
} else {
node = node->right;
while (node != nullptr && !node->leftThread) {
node = node->left;
}
}
}
}
int main() {
// 构建二叉树
TreeNode* root = new TreeNode(4);
root->left = new TreeNode(2);
root->right = new TreeNode(6);
root->left->left = new TreeNode(1);
root->left->right = new TreeNode(3);
root->right->left = new TreeNode(5);
root->right->right = new TreeNode(7);
// 执行中序线索化
TreeNode* prev = nullptr;
InorderThread(root, prev);
// 中序线索化遍历
InorderThreadTraversal(root);
std::cout << std::endl;
// 释放内存
// ...
return 0;
}
二叉树中序线索遍历
发布时间 2023-06-29 22:22:04作者: aallofitisst