来自二叉树的双线程树

我需要从常规二叉树构建双线程树，如果可能的话，使用递归。这是一个我们想要的定义：二叉树的线程化树是通过在inorder遍历中将每个空的左子节点设置为该节点的前导节点，并将每个空右子节点设置为该节点的inorder遍历中的后继节点。来自二叉树的双线程树

我无法找到一个解决方案，这里有几个类似于这个帖子，但没有解决方案。我需要的只是算法，它可以在任何语言

这是建设者，第二一个就是我需要做的：

public ThreadedNode(T theElement, ThreadedNode<T> lt, ThreadedNode<T> rt) 
{ 
    element = theElement; 
    left = lt; 
    right = rt; 
} 

public ThreadedNode(BinaryNode<T> root) 
{ 
    // implement it 
} 



//the fields 

    private T element; 

    private boolean lThread = false; 

    private ThreadedNode<T> left; 

    private boolean rThread = false; 

    private ThreadedNode<T> right; 

}

我最初的做法是调用一个辅助方法，递归，像这样：

ThreadNode<T> helper(BinaryNode<T> n, BinaryNode<T> predecessor, BinaryNode<T> successor)

，最初前任和继任者为空，但后来我下去遍历树in_order我将它们设置使用当前节点及其父，取决于它是否是左或正确的孩子，但我认为这并不适用于所有的情况下工作，我不能看如何改进它

预先感谢您

来源

2014-03-28 user1742444

左指针很容易。正确的指针有点困难。请参阅http://analgorithmaday.blogspot.com/2011/06/construct-single-threaded-binary-treein.html。另外http://stackoverflow.com/questions/1202053/right-threading-a-binary-tree?rq=1 –

非常感谢Jim，我会从你提供的2个链接中“添加”逻辑，我没有还没有找到双线程树的算法。 – user1742444

既然你提到，它可以是任何语言，here是一起提供一个C实现有非常好的解释。

来源

2014-04-15 06:42:25

来自二叉树的双线程树

回答

相关问题