给出一棵二叉树的先序遍历线索化二叉树和后序遍历线索化二叉树

### 实现二叉树的先序遍历线索化

对于二叉树的先序遍历线索化，其核心在于利用原本为空指针的位置存储指向特定节点的信息。具体来说，在先序遍历过程中：

- 如果当前节点存在左孩子，则设置该节点的`ltag=0`；否则将其`lchild`设为前驱节点地址，并令`ltag=1`。
- 对于右孩子的处理方式相同，即若有则标记为实际链接(`rtag=0`)，无则作为后继节点连接(`rtag=1`)。

此过程通过递归或迭代完成，确保每个节点都能正确指示自己的前后关系[^3]。

struct ThreadNode {
    int data;
    struct ThreadNode *lChild, *rChild;
    bool lTag, rTag; // true 表示线索 false表示正常子树
};

void preThread(ThreadNode *&p, ThreadNode *&pre) {
    if (p != NULL) {
        if (p->lChild == NULL) { // 左子树为空时建立前驱线索
            p->lTag = true;
            p->lChild = pre;
        }
        if (pre && pre->rChild == NULL) { // 右子树为空时建立后继线索
            pre->rTag = true;
            pre->rChild = p;
        }

        pre = p;

        if (!p->lTag) // 若有左子树继续线索单词它
            preThread(p->lChild, pre);
        
        if (!p->rTag)// 处理右子树
            preThread(p->rChild, pre);
    }
}

### 后序遍历线索化的实现方法

相较于先序遍历，后序遍历的特点决定了其实现逻辑有所不同。因为后序遍历时最后才访问根节点，所以在构建线索的过程中需特别注意保持正确的访问次序。通常情况下，会优先考虑左右子树再回头处理父节点的关系[^4]。

为了简化描述，这里给出一种基于栈的数据结构辅助下的非递归版本来说明如何创建后序遍历的线索链表：

// 定义一个用于保存节点及其状态（是否已处理过）的类
class StackItem {
public:
    ThreadNode* node;
    bool visited;
    
    StackItem(ThreadNode *_node): node(_node), visited(false){}
};

vector<StackItem> stack;
ThreadNode *prev = nullptr;

while(!stack.empty() || curr){
    while(curr){
        stack.push_back(StackItem(curr));
        curr = curr->left ? curr->left : curr->right;
    }
    
    auto &top = stack.back();
    if(top.visited){   
        top.node->rTag = !top.node->right;
        top.node->rChild = prev;
        prev = top.node;
        stack.pop_back();  
    }else{
        top.visited = true;
        if(stack.size()>1)
          ((stack.end()-2)->node)->rTag=true,
          ((stack.end()-2)->node)->rChild=top.node;
          
        if(!top.node->left && !top.node->right){
           top.node->lTag=true;
           top.node->lChild=((stack.size()==1)?nullptr:(stack.end()-2))->node;
        }
        curr = top.node->right ? top.node->right : top.node->left;
    }
}

if(prev){
   prev->rTag=false;
   prev->rChild=nullptr;
}

上述代码片段展示了如何使用栈来进行后序遍历的同时完成线索化的工作。需要注意的是，这段程序假设输入是一棵完整的二叉树，并且所有节点都遵循相同的定义模式。