我需要从常规二叉树构建双线程树,如果可能的话使用递归 . 这是我们使用的定义:二叉树的线程树是通过将每个空左子项设置为inorder遍历中的节点的前任,并将每个null右子项设置为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)
,最初的前任和后继是null,但是当我走下去遍历树时 in_order
我使用当前节点及其父节点设置它们,具体取决于它是左边还是右边的孩子,但我认为它不适用于所有情况我不知道如何改进它
先感谢您
1 回答
既然你提到它可以是任何语言,here是一个C实现提供的非常好的解释 .