c++实现二叉树中序线索化完成中序遍历

二叉树的线索化，可以将空指针域利用起来，将二叉树中的空指针指向该节点中序遍历的前驱或后继节点，从而将递归的中序遍历转化为线性的遍历。下面是使用中序线索化完成的中序遍历的C++代码：

#include<iostream>

using namespace std;

//定义二叉树结点
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    bool ltag;  //标记左指针是否为线索
    bool rtag;  //标记右指针是否为线索
    TreeNode(int x) : val(x), left(NULL), right(NULL), ltag(false), rtag(false) {}
};

//中序线索化二叉树
void InThread(TreeNode* &p, TreeNode* &pre) {
    if (p != NULL) {
        InThread(p->left, pre);
        if (p->left == NULL) {
            p->ltag = true;
            p->left = pre;
        }
        if (pre != NULL && pre->right == NULL) {
            pre->rtag = true;
            pre->right = p;
        }
        pre = p;
        InThread(p->right, pre);
    }
}

//中序遍历线索化二叉树
void InThreadOrder(TreeNode* p) {
    while (p != NULL) {
        while (p->ltag == false) {
            p = p->left;
        }
        cout << p->val << " ";
        while (p->rtag == true && p->right != NULL) {
            p = p->right;
            cout << p->val << " ";
        }
        p = p->right;
    }
}

//测试
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 = NULL;
    InThread(root, pre);

    cout << "中序遍历结果：";
    InThreadOrder(root);
    cout << endl;

    return 0;
}

以上代码中，InThread函数实现了中序线索化，InThreadOrder函数实现了中序遍历线索化二叉树的操作。在main函数中，我们构造了一个简单的二叉树，并进行了中序线索化和中序遍历的测试。