이진 트리 오른쪽 스레딩

Question

나는 이것을 이해하려고 오랜 시간을 보내고 있습니다. 내가 본 모든 곳에서 실제로 목록에서 비 반복적으로 (실제로 이해할 수있는 부분을) 통과하는 방법에 대한 설명으로 만 실행되는 것처럼 보입니다. 거기에 아무도 밖으로 망치질 수있는 정확히 처음에 목록을 통해 갈 수있는 노드 클래스에서 플래그를 수 있도록 실제 선행/후임 노드를 찾으십시오? 간단한 바이너리 검색 트리를 만들고 목록을 살펴보고 이전 링크/후속 링크에 대한 null 링크를 다시 라우팅 할 수 있어야합니다. 나는 다소 다음과 같은 솔루션과 약간의 행운을 했어 :

당신의 설명에서

thread(node n, node p) { 
    if (n.left !=null) 
     thread (n.left, n); 
    if (n.right !=null) { 
     thread (n.right, p); 
    } 
    n.right = p; 
} 

Answer 1

, 난 당신이 같은 구조를보고 뭔가 노드가 가정합니다 :

Node { 
    left 
    right 
} 

을 ... 왼쪽과 오른쪽을 사용하여이 2 진 트리가 설정되어 있고 트리의 깊이 첫 탐색에서 이중 연결 목록을 만들기 위해 값을 왼쪽과 오른쪽으로 다시 할당하려고한다고 가정합니다.

지금까지 살펴본 내용에 대한 근본적인 (말장난 없음) 문제는 탐색 중에 전달되는 "노드 p"(이전의?)가 트리에서 현재 트리의 위치와 독립적이어야한다는 것입니다 항상 이전에 방문한 노드가 있어야합니다. 이를 수행하기 위해 스레드가 실행될 때마다 동일한 "이전"변수를 참조해야합니다. 나는 하나의 C-ism을 가진 Python-ish 의사 코드를 작성했다. 익숙하지 않은 경우 '&'은 "참조"(또는 C#의 "ref")를 의미하고 '*'는 참조 취소 및 나에게 그것이 가리키고있는 물건을주세요. " 당신은 C에서 이것을 구현하려고한다면

Node lastVisited 
thread(root, &lastVisisted) 

function thread(node, lastVisitedRef) 
    if (node.left) 
    thread(node.left, lastVisitedRef) 
    if (node.right) 
    thread(node.right, lastVisitedRef) 

    // visit this node, reassigning left and right 
    if (*lastVisitedRef) 
    node.right = *lastVisitedRef 
    (*lastVisitedRef).left = node 
    // update reference lastVisited 
    lastVisitedRef = &node 

, 당신은 참조를 보유하는 이중 포인터를 필요로 실제로 싶지만, 아이디어는 동일합니다 - 당신이 "마지막 방문 노드"의 위치를 ​​유지하기 위해 필요 전체 순회 중.