algorithm - 二叉树中的双线程树

我需要从普通的二叉树构建一个双线程树，如果可能的话使用递归。
这就是我们正在使用的定义：二叉树的线程树是通过将每个空的左子节点设置为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;

}

我的初始方法是递归地调用helper方法，如下所示：
ThreadNode<T> helper(BinaryNode<T> n, BinaryNode<T> predecessor, BinaryNode<T> successor)
，最初前置和后继是空的，但是当我向下遍历树时，我使用当前节点及其父节点设置它们，这取决于它是左子节点还是右子节点，但我认为这并不适用于所有情况，我看不出如何改进它。
提前谢谢你

最佳答案

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