이진 트리에서 이중 스레드 트리

가능하면 재귀를 사용하여 일반 이진 트리에서 이중 스레드 트리를 작성해야합니다. 이것은 정의입니다 : 2 진 트리의 스레드 된 트리는 inorder traversal에서 모든 null 왼쪽 자식을 inorder traversal에서 노드의 선행자로 설정하고 모든 null 권한 아이를 inorder traversal에서 노드의 후속 노드로 설정하여 얻습니다. .이진 트리에서 이중 스레드 트리

나는 이것에 대한 해결책을 찾을 수 없으며 여기에 해결책이없는 두 개의 게시물이 있습니다. 재귀,

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; 

}

내 초기 접근 방식은 도우미 메서드를 호출하는 것입니다 : 난 그냥 알고리즘을 필요가

이 생성자는 어떤 언어로 할 수있다, 2 일 내가해야 할 일입니다 이 같은 :

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

, 처음 전임자와 후임자가 null입니다,하지만 나는 그것이 왼쪽 또는 여부에 따라, 현재 노드 및 그 부모를 사용하여 설정 트리 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 –

짐 감사합니다, 당신이 제공 한 2 개의 링크에서 로직을 "추가"할 것입니다. 아직 이중 스레드 트리에 대한 알고리즘을 찾지 못했습니다. – user1742444

에 감사를 개선하는 방법을 볼 수 없습니다, here는 함께 제공되는 C 구현입니다 아주 좋은 설명과 함께.

출처

2014-04-15 06:42:25

이진 트리에서 이중 스레드 트리

답변

관련 문제