從二叉樹實現二叉樹實現的線程

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.