从二叉树实现二叉树实现的线程

Question

我正在为学校做作业。它由一个方法组成，它将一个二叉树作为输入并返回一个双线程树。例如（如果左边的孩子= null，那么左边的孩子将与先前的中间父亲连接，如果右边的孩子= null，则它将连接到其中序列的连接符。现在，因为我的老师的实现要求线程树是与二进制类不同的类，我必须再遍历二叉树，并将每个节点从binaryNode转换为threadedNode，从而使得在最后一个“重复”的初始BinaryTree，但是作为Threadedtree类型，当我这样做后，我再次遍历这个ThreadTree，并且每当我看到一个空的左侧或右侧的孩子时，我都会引用inorder arraylist并查找线程。

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

这是方法由导师

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

Answer 1

你可以跳过您在法提遍历的第二次指定。您可以即时将节点从BinaryNode转换为ThreadedNode。我认为，您仍然需要遍历两次，以进行inorder遍历，并找到线程并将其转换为ThreadedTree。

对于即时转换，您可以使用您的教师提供的方法。

HTH！

Answer 2

指导员是正确的。一次遍历就足够了。

遍历原始的二叉树，当你走这棵树时创建新的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，它没有正确的子节点，所以添加一个从D到B的带螺纹的右指针。然后设置在B之前并继续。接下来你击中A.B没有正确的孩子，所以添加一个从B到A的正确的链接.A有一个正确的孩子继续，设置在A之前。下一个节点是C. C没有离开孩子，所以添加一个从C中的左侧链接到前一个的当前值，即A.