java - 用于预排序线程二叉搜索树的插入函数

Question

我正在尝试以一种终端（叶节点）节点的左子节点的方式制作一棵树。
链接以查看树的外观。

我得到了我想要的代码的无序版本，它是一个简单的插入函数，可以线程化树，但现在我的问题是将此代码更改为 preOrder 插入。

这是我可以做到的，但我的主要问题是找到预购后继者，它一直在另一个子树中，你们中的任何人都知道获得预购后继者的简单方法吗？

//in-order insert
if (root == null) {                  // tree is empty
    root = newNode;
    return;
}
PreNode<T> p = root, prev = null;
    while (p != null) {              // find a place to insert newNode;
    prev = p;
    if (info.compareTo(p.info) < 0)
        p = p.left;
    else if (!p.hasThread)           // go to the right node only if it is
        p = p.right;                 // a descendant, not a successor;
    else break;                      // don't follow successor link;
}

if (info.compareTo(prev.info) < 0) { // if newNode is left child of
    prev.left  = newNode;            // its parent, the parent becomes
    newNode.hasThread = true;        // also its successor;
    newNode.right = prev;
}
else if (prev.hasThread) {           // if parent of the newNode
    newNode.hasThread = true;        // is not the right-most node,
    prev.hasThread = false;          // make parent's successor
    newNode.right = prev.right;      // newNode's successor,
    prev.right = newNode;
}
else prev.right = newNode;           // otherwise has no successor;

Answer 1

这将起作用，假设有一个 Node 类具有对其子级的左右引用以及一个布尔变量ht，该变量指示它是否具有线程。

public void insert(T info) {
        PreNode<T> newNode = new PreNode<T>(info);
        if (root == null) {
            root = newNode;
            return;
        }
        PreNode<T> curr = root, r = null, l = null;
        while (true) {
            if (info.compareTo(curr.info) < 0) {

                if (curr.right != null)
                    r = curr.right;

                if (curr.left == null || curr.ht) {
                    newNode.left = r;
                    curr.left = newNode;
                    curr.ht = false;
                    return;
                } else
                    curr = curr.left;
            } else {
                if (curr.left != null && !curr.ht)
                    l = curr.left;

                if (curr.right == null) {

                    if (curr.ht) {
                        newNode.left = curr.left;
                        newNode.ht = true;
                        curr.left = null;
                        curr.right = newNode;
                        curr.ht = false;
                        return;
                    } else
                        newNode.left = r;

                    curr.right = newNode;
                    curr.ht = false;

                    if (l != null) {
                        while (!l.ht) {
                            if (l.right != null)
                                l = l.right;
                            else
                                l = l.left;
                        }
                        l.left = newNode;
                        l.ht = true;
                        return;
                    }
                } else
                    curr = curr.right;
            }
        }
    }