java - プレオーダー スレッド化二分探索木の挿入関数

Question

ターミナル（リーフノード）ノードの左の子になるように、ツリーを作成しようとしています。
リンクをクリックして、ツリーがどのように見えるかを確認してください。

ツリーをスレッド化する単純な挿入関数であるコードの inorder バージョンを取得しましたが、このコードを 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

これは、子への左右の参照とht、スレッドがあるかどうかを示すブール変数を持つ Node クラスがあると仮定して機能します。

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;
            }
        }
    }