左线索二叉搜索树中序遍历陷入无限循环问题求助

你遇到的无限循环问题，核心原因是递归中序遍历没有区分左指针是「左孩子节点」还是「前驱线索」。左线索二叉树中，lthread标志为true时，left指针指向的是当前节点的中序前驱节点，而非左孩子，直接递归这个指针会导致程序回到之前的节点，陷入循环。

具体问题拆解 #

看你的插入逻辑：当插入右节点时（比如0作为-1的右孩子），新节点的left会被设置为父节点（-1），且lthread保持初始的true（左线索）。此时你的递归遍历代码：

if (p->left) InOrder(p->left);

会因为0->left存在（指向-1），直接递归调用InOrder(-1)，而-1的右孩子又是0，这样就形成了-1 → 0 → -1的无限递归循环，最终重复打印这两个节点的信息。

修复后的遍历代码 #

修改递归逻辑，只有当lthread为false时，才说明left是左孩子节点，需要递归遍历；同时增加空节点判断，避免空指针访问：

void InOrder(thnode *root) {
    if (root == nullptr) return; // 先处理空节点，防止崩溃
    thnode *p = root;

    // 仅当lthread为false时，left是左孩子，递归遍历左子树
    if (!p->lthread) {
        InOrder(p->left);
    }

    // 打印节点信息
    cout << p->info << ",";
    cout << (p->left ? to_string(p->left->info) : "null") << ",";
    cout << (p->lthread ? "T" : "F") << endl;

    // 右指针是正常的孩子节点，存在则递归遍历右子树
    if (p->right) {
        InOrder(p->right);
    }
}

额外说明 #

你的左线索二叉树插入逻辑是正确的：

• 当节点作为左孩子插入时，父节点的lthread设为false（表示left是左孩子）
• 当节点作为右孩子插入时，自身的left设为父节点（前驱线索），lthread保持true

只要遍历逻辑区分开「左孩子」和「左线索」，就能避免无限循环，正确完成中序遍历。

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