实验七-JZTXT

#include <iostream>

struct TreeNode {
int data;
TreeNode* left;
TreeNode* right;
bool isThreaded;  // 标志指示是否是线索
TreeNode(int val) : data(val), left(nullptr), right(nullptr), isThreaded(false) {}
};

// 创建线索二叉树
TreeNode* createThreadedBinaryTree(int data) {
    return new TreeNode(data);
}

// 对线索二叉树进行中序线索化
TreeNode* prev = nullptr;  // 用于跟踪前一个节点

void threadBinaryTree(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    // 递归左子树
    threadBinaryTree(root->left);

    // 处理当前节点
    if (prev != nullptr) {
        if (prev->right == nullptr) {
            prev->right = root;
            prev->isThreaded = true;
        }
    }

    // 更新prev为当前节点
    prev = root;

    // 递归右子树
    threadBinaryTree(root->right);
}

// 中序遍历线索二叉树
void inorderTraversal(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    // 找到中序遍历的第一个节点
    while (root != nullptr && !root->isThreaded) {
        root = root->left;
    }

    while (root != nullptr) {
        std::cout << root->data << " ";

        // 如果节点有线索，直接跳到后继节点
        if (root->isThreaded) {
            root = root->right;
        } else {
            // 否则，移动到右子树中的最左节点
            root = root->right;
            while (root != nullptr && !root->isThreaded) {
                root = root->left;
            }
        }
    }
}

int main() {
    TreeNode* root = createThreadedBinaryTree(4);
    root->left = createThreadedBinaryTree(2);
    root->right = createThreadedBinaryTree(6);
    root->left->left = createThreadedBinaryTree(1);
    root->left->right = createThreadedBinaryTree(3);
    root->right->left = createThreadedBinaryTree(5);
    root->right->right = createThreadedBinaryTree(7);

    // 对二叉树进行线索化
    threadBinaryTree(root);

    // 中序遍历线索二叉树
    std::cout << "Inorder Traversal: ";
    inorderTraversal(root);
    std::cout << std::endl;

    return 0;
}