写一个二叉树的的遍历与线索化

二叉树的遍历包括前序遍历、中序遍历和后序遍历，其中前序遍历的遍历顺序是先根节点，然后左子树，最后右子树；中序遍历的遍历顺序是先左子树，然后根节点，最后右子树；后序遍历的遍历顺序是先左子树，然后右子树，最后根节点。

二叉树的线索化是将二叉树中的空指针指向该节点的前驱或后继，这样可以避免遍历时的空指针判断，提高遍历效率。线索化分为前序线索化、中序线索化和后序线索化。

以下是C++代码实现：

//定义二叉树节点
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    bool leftIsThread; //是否左线索
    bool rightIsThread; //是否右线索
    TreeNode(int x) : val(x), left(nullptr), right(nullptr), leftIsThread(false), rightIsThread(false) {}
};

//前序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    std::cout << root->val << " ";
    if (root->leftIsThread) {
        preOrder(root->left);
    }
    if (root->rightIsThread) {
        preOrder(root->right);
    }
}

//中序遍历
void inOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    if (root->leftIsThread) {
        inOrder(root->left);
    }
    std::cout << root->val << " ";
    if (root->rightIsThread) {
        inOrder(root->right);
    }
}

//后序遍历
void postOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }
    if (root->leftIsThread) {
        postOrder(root->left);
    }
    if (root->rightIsThread) {
        postOrder(root->right);
    }
    std::cout << root->val << " ";
}

//前序线索化
void preOrderThreading(TreeNode* root, TreeNode*& pre) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr) {
        root->left = pre;
        root->leftIsThread = true;
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = root;
        pre->rightIsThread = true;
    }
    pre = root;
    if (!root->leftIsThread) {
        preOrderThreading(root->left, pre);
    }
    if (!root->rightIsThread) {
        preOrderThreading(root->right, pre);
    }
}

//中序线索化
void inOrderThreading(TreeNode* root, TreeNode*& pre) {
    if (root == nullptr) {
        return;
    }
    if (!root->leftIsThread) {
        inOrderThreading(root->left, pre);
    }
    if (root->left == nullptr) {
        root->left = pre;
        root->leftIsThread = true;
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = root;
        pre->rightIsThread = true;
    }
    pre = root;
    if (!root->rightIsThread) {
        inOrderThreading(root->right, pre);
    }
}

//后序线索化
void postOrderThreading(TreeNode* root, TreeNode*& pre) {
    if (root == nullptr) {
        return;
    }
    if (!root->leftIsThread) {
        postOrderThreading(root->left, pre);
    }
    if (!root->rightIsThread) {
        postOrderThreading(root->right, pre);
    }
    if (root->left == nullptr) {
        root->left = pre;
        root->leftIsThread = true;
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = root;
        pre->rightIsThread = true;
    }
    pre = root;
}

//测试代码
int main() {
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->right->left = new TreeNode(6);
    root->right->right = new TreeNode(7);

    //前序线索化
    TreeNode* pre = nullptr;
    preOrderThreading(root, pre);
    std::cout << "前序线索化遍历：";
    TreeNode* p = root;
    while (p != nullptr) {
        std::cout << p->val << " ";
        if (p->leftIsThread) {
            p = p->left;
        } else {
            p = p->right;
        }
    }
    std::cout << std::endl;

    //中序线索化
    pre = nullptr;
    inOrderThreading(root, pre);
    std::cout << "中序线索化遍历：";
    p = root->left->left;
    while (p != nullptr) {
        std::cout << p->val << " ";
        if (p->rightIsThread) {
            p = p->right;
        } else {
            p = p->right->left;
        }
    }
    std::cout << std::endl;

    //后序线索化
    pre = nullptr;
    postOrderThreading(root, pre);
    std::cout << "后序线索化遍历：";
    p = root->left->left;
    while (p != nullptr) {
        std::cout << p->val << " ";
        if (p->leftIsThread) {
            p = p->left;
        } else {
            p = p->left->right;
        }
    }
    std::cout << std::endl;

    return 0;
}