二叉树的双线程树

Question

我需要从一个常规的二叉树构建一个双线程树，如果可能的话使用递归。这就是我们USIG的定义：二叉树的线程树是通过在顺序遍历中将每一个null左子设为节点的前导子，在顺序遍历中将每一个null右子设为节点的后继子而得到的。

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

这是构造函数，第二个是我需要做的：

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 助手(BinaryNode n、BinaryNode 前任、BinaryNode 后继）

Answer 1

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