指導員是正確的。一次遍歷就足夠了。
遍歷原始的二叉樹,當你走這棵樹時創建新的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.
你是什麼意思? – user1072706