二叉树的中序线索化及其非栈非递归遍历代码

以下是二叉树的中序线索化及其非栈非递归遍历的C++代码实现：

#include <iostream>
#include <queue>
using namespace std;

// 节点结构体
struct Node {
    int val;
    Node* left;
    Node* right;
    bool ltag, rtag;    // 线索标记
    Node(int v) : val(v), left(NULL), right(NULL), ltag(false), rtag(false) {}
};

// 中序线索化
void InOrderThread(Node* p, Node* &pre) {
    if (!p) return;
    InOrderThread(p->left, pre);
    if (!p->left) {
        p->ltag = true;
        p->left = pre;
    }
    if (pre && !pre->right) {
        pre->rtag = true;
        pre->right = p;
    }
    pre = p;
    InOrderThread(p->right, pre);
}

// 非栈非递归遍历
void InOrderNonRecursive(Node* root) {
    Node* pre = NULL;
    Node* cur = root;
    while (cur) {
        if (!cur->ltag) {
            cur = cur->left;
        } else {
            cout << cur->val << " ";
            pre = cur;
            cur = cur->rtag ? cur->right : cur->right->left;
        }
    }
}

int main() {
    // 构造二叉树
    Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);

    // 中序线索化
    Node* pre = NULL;
    InOrderThread(root, pre);

    // 非栈非递归遍历
    cout << "InOrderNonRecursive: ";
    InOrderNonRecursive(root);
    cout << endl;

    return 0;
}

在本代码中，我们首先定义了节点结构体，并在其中增加了左右指针和线索标记。然后，我们实现了中序线索化算法 `InOrderThread`，该算法使用递归方式中序遍历二叉树，并将空指针域改为指向该节点在中序遍历中的前驱或后继节点。最后，我们实现了非栈非递归遍历算法 `InOrderNonRecursive`，该算法使用指针变量来记录当前节点的前驱或后继节点，避免重复遍历，从而高效地遍历线索二叉树。

在主函数中，我们构造了一个二叉树，并进行了中序线索化和非栈非递归遍历，最后输出遍历结果。

希望本代码可以帮助您更好地理解二叉树的中序线索化及其非栈非递归遍历算法。