关于二叉树先序线索化的理解是否正确？附中序线索化代码

先明确你给出的二叉树结构：

A
   / \
  B   C
 / \
D   E

你的理解是错误的，先序线索化的核心规则是只修改原本为空的左/右指针，将其替换为线索指针；原本有子节点的指针不会被改动。

先序线索化的核心逻辑 #

先序遍历序列是ABDEC，线索化时：

• 每个节点的左线索指向先序前驱，右线索指向先序后继
• 只有当节点原本没有左孩子（l_child为NULL）时，才会设置左线索；原本没有右孩子时，才会设置右线索

针对根节点A的正确处理 #

• A本身有左孩子B、右孩子C，所以它的l_child和r_child会保持原指向，不会被改成NULL或D
• A的先序前驱不存在，若使用带头结点的线索二叉树，A的左线索会指向头结点；若不带头结点，A的左指针因存在左孩子，不会被设置为线索
• A的先序后继是B，不是D——先序遍历是“根→左子树→右子树”的顺序，A之后直接访问B，D是B的后继

附：你提供的中序线索化代码说明 #

你给出的代码是标准的中序线索化实现，逻辑是“左子树递归→当前节点线索处理→右子树递归”，和先序线索化的“当前节点处理→左子树递归→右子树递归”逻辑不同：

void in_thread(struct node* root, struct node** parent) {
    if (root != NULL) {
        // 先递归处理左子树
        in_thread(root->l_child, parent);
        // 处理当前节点的线索
        if (root->l_child == NULL) {
            root->ltag = 1;
            root->l_child = (*parent);
        }
        if ((*parent) != NULL && (*parent)->r_child == NULL) {
            (*parent)->rtag = 1;
            (*parent)->r_child = root;
        }
        (*parent) = root;
        // 最后递归处理右子树
        in_thread(root->r_child, parent);
    }
}

内容的提问来源于stack exchange，提问作者Tyler233