C++中实现线索化二叉搜索树的难点求助

我在C++中实现线索化二叉搜索树（Threaded Binary Search Tree）时遇到瓶颈，目前已完成非线索化树的实现，但核心难点是不使用显式父指针的前提下，正确设置指向前驱/后继节点的线索。

问题集中在inserthelp()函数：尝试用数组记录前驱节点来确定线索但失败，需要调整以下部分：

• BSTNode类的构造函数、setLeft/setRight函数，在合适时机分配线索并设置isLeftThread/isRightThread标记
• 修改BST类的printHelp和printInOrder函数，利用线索完成遍历

额外要求：

• printInOrder和print尽量避免递归，改用while循环实现
• 不存储显式父节点指针
• printInOrder不能使用栈或节点列表，仅依赖当前节点及其指向的节点

下方是可正常运行的非线索化树代码，需要改造为线索化版本：

using namespace std;

#include <iostream>
#include <stack> // want to avoid needing this
#include <string>

template <typename E>
class BinNode {};

template <typename Key, typename E>
class BSTNode : public BinNode<E> {
 public:
  E it;
  BSTNode* lp;
  BSTNode* rp;
  bool isLpChildPointer;
  bool isRpChildPointer;
  bool isLeftThreaded;
  bool isRightThreaded;
  Key k;
  BSTNode() { lp = rp = NULL; }
  BSTNode(Key K, E e, BSTNode* l, BSTNode* r) {
    k = K;
    it = e;
    lp = l;
    rp = r;
    isLpChildPointer = false;
    isRpChildPointer = false;
    isLeftThreaded = true;
    isRightThreaded = true;
  }
  void setLeft(BinNode<E>* b) {
    lp = (BSTNode*)b;
    isLpChildPointer = true;
    isLeftThreaded = false;
  }

  void setRight(BinNode<E>* b) {
    rp = (BSTNode*)b;
    isRpChildPointer = true;
    isRightThreaded = false;
  }
};

template <typename Key, typename E>
class BST {
 public:
  BSTNode<Key, E>* root;
  int nodecount;

  BSTNode<Key, E>* inserthelp(BSTNode<Key, E>*, const Key&, const E&,
                              BSTNode<Key, E>*[], int, int);
  void printhelp(BSTNode<Key, E>* root, int level) const {
    if (root == NULL) return;
    printhelp(root->lp, level + 1);
    for (int i = 0; i < level; i++) cout << "  ";
    cout << root->k << "\n";
    printhelp(root->rp, level + 1);
  }

  BST() {
    root = NULL;
    nodecount = 0;
  }

  void printInOrder() {
    std::stack<BSTNode<Key, E>*> stack; // how to get rid of stack here and only use while // loop, using only lp and rp to access all nodes
    BSTNode<Key, E>* current = root;
    while (current != nullptr || !stack.empty()) {
      while (current != nullptr) {
        stack.push(current);
        current = current->lp;
      }
      current = stack.top();
      cout << current->it << endl;
      stack.pop();
      current = current->rp;
    }
  }

  void insert(const Key& k, const E& e) {
    root = inserthelp(k, e, root);
    nodecount++;
  }

  BSTNode<Key, E>* inserthelp(const Key& k, const E& e, BSTNode<Key, E>* node) {
    if (node == nullptr) {
      return new BSTNode<Key, E>(k, e, NULL, NULL); // what to put here instead of NULL. 
                                                    // and how to keep track of what higher level nodes this new node should thread to.
    } else {
      if (k < node->k) {
        node->setLeft(inserthelp(k, e, node->lp));
      } else {
        node->setRight(inserthelp(k, e, node->rp));
      }
      return node;
    }
  }
  void print() const { printhelp(root, 0); }
};

int main() {
  BST<int, string> tree;

  tree.insert(77, "seventy-seven");
  tree.insert(70, "seventy");
  tree.insert(75, "seventy-five");
  tree.insert(66, "sixty-six");
  // other inserts...
  tree.insert(83, "eighty-three");
  tree.insert(87, "eighty-seven");
  tree.insert(65, "sixty-five");

  tree.print();
  tree.printInOrder();
}

以下是符合要求的线索化BST实现，核心解决了插入时的线索维护和无栈遍历问题：

using namespace std;

#include <iostream>
#include <queue>
#include <string>

template <typename E>
class BinNode {};

template <typename Key, typename E>
class BSTNode : public BinNode<E> {
public:
    E it;
    BSTNode* lp;
    BSTNode* rp;
    bool isLeftThread;  // true = 左指针是线索（指向前驱），false = 左指针是子节点
    bool isRightThread; // true = 右指针是线索（指向后继），false = 右指针是子节点
    Key k;

    // 构造新节点：默认左右都是线索（初始指向NULL，插入时会修正）
    BSTNode(Key K, E e) : k(K), it(e), lp(nullptr), rp(nullptr), isLeftThread(true), isRightThread(true) {}
};

template <typename Key, typename E>
class BST {
private:
    // 辅助插入函数：传递父节点上下文，用于设置线索
    BSTNode<Key, E>* inserthelp(BSTNode<Key, E>* node, const Key& k, const E& e, BSTNode<Key, E>* parent) {
        if (node == nullptr) {
            BSTNode<Key, E>* newNode = new BSTNode<Key, E>(k, e);
            if (parent == nullptr) {
                // 根节点，无父节点，线索保持NULL
                return newNode;
            }
            // 根据插入位置设置线索
            if (k < parent->k) {
                // 插入到父节点左侧：新节点的右线索指向父节点，左线索继承父节点原左线索
                newNode->rp = parent;
                newNode->lp = parent->lp;
            } else {
                // 插入到父节点右侧：新节点的左线索指向父节点，右线索继承父节点原右线索
                newNode->lp = parent;
                newNode->rp = parent->rp;
            }
            return newNode;
        }

        if (k < node->k) {
            if (!node->isLeftThread) {
                // 左是子节点，递归插入左子树
                node->lp = inserthelp(node->lp, k, e, node);
            } else {
                // 左是线索，直接替换为新节点，并更新标记
                node->lp = inserthelp(nullptr, k, e, node);
                node->isLeftThread = false;
            }
        } else if (k > node->k) {
            if (!node->isRightThread) {
                // 右是子节点，递归插入右子树
                node->rp = inserthelp(node->rp, k, e, node);
            } else {
                // 右是线索，直接替换为新节点，并更新标记
                node->rp = inserthelp(nullptr, k, e, node);
                node->isRightThread = false;
            }
        }
        // 忽略重复键
        return node;
    }

public:
    BSTNode<Key, E>* root;
    int nodecount;

    BST() : root(nullptr), nodecount(0) {}

    // 无栈无递归中序遍历
    void printInOrder() {
        if (root == nullptr) return;

        BSTNode<Key, E>* current = root;
        // 先找到最左节点（中序第一个节点）
        while (!current->isLeftThread) {
            current = current->lp;
        }

        while (true) {
            cout << current->it << endl;

            // 如果右是线索，直接跳转到后继
            if (current->isRightThread) {
                current = current->rp;
                // 回到根节点的后继（NULL）时结束
                if (current == nullptr) break;
            } else {
                // 否则转到右子树的最左节点
                current = current->rp;
                while (!current->isLeftThread) {
                    current = current->lp;
                }
            }
        }
    }

    void insert(const Key& k, const E& e) {
        root = inserthelp(root, k, e, nullptr);
        nodecount++;
    }

    // 非递归缩进打印（层次遍历）
    void print() const {
        if (root == nullptr) return;

        queue<pair<BSTNode<Key, E>*, int>> q;
        q.push({root, 0});

        while (!q.empty()) {
            auto [node, level] = q.front();
            q.pop();

            // 打印缩进
            for (int i = 0; i < level; i++) {
                cout << "  ";
            }
            cout << node->k << "\n";

            // 左是子节点则入队
            if (!node->isLeftThread) {
                q.push({node->lp, level + 1});
            }
            // 右是子节点则入队
            if (!node->isRightThread) {
                q.push({node->rp, level + 1});
            }
        }
    }
};

int main() {
    BST<int, string> tree;

    tree.insert(77, "seventy-seven");
    tree.insert(70, "seventy");
    tree.insert(75, "seventy-five");
    tree.insert(66, "sixty-six");
    tree.insert(83, "eighty-three");
    tree.insert(87, "eighty-seven");
    tree.insert(65, "sixty-five");

    cout << "缩进打印（层次遍历）:\n";
    tree.print();
    cout << "\n中序遍历（无栈）:\n";
    tree.printInOrder();
}

1. 节点结构简化：
   移除了冗余的标记字段，只用isLeftThread和isRightThread区分指针类型，逻辑更清晰，减少出错概率。

2. 插入时的线索维护：
   递归插入时通过参数传递父节点，新节点根据插入位置（左/右）自动继承父节点的对应线索，并将自身的另一线索指向父节点，同时更新父节点的指针标记为子节点。

3. 无栈中序遍历：
   利用线索直接跳转，无需栈辅助：

   • 起始时找到最左节点（中序第一个节点）
   • 访问节点后，若右指针是线索则直接跳转到后继；否则进入右子树的最左节点
   • 循环直到回到根节点的后继（NULL）

4. 非递归缩进打印：
   使用队列实现层次遍历，记录每个节点的层级，根据层级输出缩进，完全替代原递归实现。

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