java - 二叉树的线程二叉树实现

Question

我正在为学校做作业。它主要由一个方法组成，该方法将二叉树作为输入并返回双线程树。例如(如果 left child = null 那么 left child 将与前面的 inorder parent 连接，如果 right child = null 它将链接到它的 inorder successor。现在我有一个实现的想法......

我通过原始二叉树递归迭代并将中序遍历存储到数组中。现在，因为我的老师实现要求线程树与二进制树不同。我必须再次遍历二叉树并将每个节点从 binaryNode 转换为 threadedNode 从而在最后具有初始 BinaryTree 的“副本”但是作为 Threadedtree 类型。执行此操作后，我再次遍历此 threadedTree，每当我看到一个 null 的左或右子节点时，我都会引用 inorder arraylist 并找到线程。

现在你可能已经注意到这是非常低效的，我基本上遍历了树 3 次。我的教授表示，这可以通过一次遍历递归完成，本质上是转换为 threadedNode 并一次找到所有线程。我尝试了多种方法，但找不到有效的方法。有没有人有任何提示或某种方式我可以实现它？谢谢

这是老师指定的方法

public static <T> ThreadedNode<T> thread(BinaryNode<T> root)
{
   //threads a binary tree
}

Answer 1

老师是对的。一次遍历就足够了。

遍历原始二叉树，在遍历这棵树时创建新的 ThreadedNode。

public static <T> ThreadedNode<T> thread(BinaryNode<T> root) {
    // We'll be keeping track of the "previous" node as we go, so use
    // a recursive helper method.  At first, there is no previous.
    return threadHelper(root, null);
}

private static <T> ThreadedNode<T> threadHelper(BinaryNode<T> n, ThreadedNode<T> previous) {

    // Create a new threaded node from the current root.  Note that the threaded nodes
    // are actually created in "preorder".  Assume the ThreadedNode constructor sets
    // the left, right, threadLeft, and threadRight fields to null.
    ThreadedNode<T> t = new ThreadedNode<T>(n.getData());

    // First go down the left side, if necessary.
    if (n.getLeft() != null) {
        // If there is a left child we have to descend.  Note that as we go down the
        // left side the previous doesn't change, until we start "backing up".
        t.left = threadHelper(n.getLeft(), previous);
        previous = t.left;
    } else {
        // If there is no left child, connect our left thread to the previous.
        t.threadLeft = previous;
    }

    // Now before we go down the right side, see if the previous
    // node (it will be in the left subtree) needs to point here.
    if (previous != null && previous.right == null) {
        previous.threadRight = t;
    }

    if (n.getRight() != null) {
        // If there is a right child we can descend the right.  As we go down we
        // update previous to the current node.  We do this just by passing the current
        // node as the second parameter.
        t.right = threadHelper(n.getRight(), t);
    } else {
        // No right child, no worries.  We'll hook up our thread-right pointer
        // later.
    }
    return t;
}

考虑树 (A (B (D) ()) C)。你在中序遍历中遇到的第一个节点是 D。没有前一个节点。所以像以前一样保存D。那么你下一个命中的节点是B。之前的节点是D，它没有右 child ，所以在D到B添加一个线程右指针。然后将previous设置为B并继续。接下来你点击 A。B 没有右 child ，所以添加一个从 B 到 A 的线程右链接。A 有一个右 child 所以继续，设置 previous 到 A。下一个节点是 C。C 没有左 child ，所以添加一个线程左链接从 C 到 previous 的当前值，即 A。