首页 文章

二叉树的双线程树

提问于
浏览
1

我需要从常规二叉树构建双线程树,如果可能的话使用递归 . 这是我们使用的定义:二叉树的线程树是通过将每个空左子项设置为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 回答

  • 0

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

相关问题