inorder 순회 BST

Question

재귀 inorder 이진 검색 트리 순회에서 이전 노드를 추적하는 방법?

eq ... ... bst ... 내에서 주어진 값보다 큰 bst의 첫 번째 숫자를 찾으려고합니다. 그 시점에서 이전의 데이터를 인쇄합니다. 동일하거나 탐색 inorder를 그대로 주어진 값 적은 다음 중 하나입니다 노드 ...

그래서 질문은 우리가 통과 중위 재귀에 BST에서 이전 노드를 추적 할 수있는 방법을 왜 ??

Answer 1

이진 트리 재귀는 왼쪽 트리를 누른 다음 오른쪽으로 이동하여 작동합니다. Inorder/preorder/postorder는 재귀 적 프로 시저에서 일부 로컬 작업의 순서에 따라 결정되는 규칙입니다. 두 개의 재귀 호출과 관련하여 현재 노드 자체의 "방문"타이밍입니다.

다음 노드를 얻는 방법은 재귀가 반환하도록하는 것입니다.

트리로 돌아갈 때 "inorder"에서 마지막으로 방문한 노드는 단순히 맨 오른쪽 노드입니다. 따라서 재귀는 가장 오른쪽 노드 만 리턴해야합니다.

또한, 전체적으로 트리 T가 이전 노드 P를 갖는 경우, T의 좌측 서브 트리, 즉 좌측 (T)도 동일한 이전 노드 P를 갖는다. P는 T의 가장 좌측 노드의 전신이다.

또한 오른쪽 (T)에 대한 이전 노드는 노드 T 자체입니다.

그래서 왼쪽으로 재귀 (T) 할 때 우리는 단순히 우리에게 주어진 전임자를 거절 할 수 있습니다. 그리고 오른쪽으로 재귀 (T) 할 때 우리는 전임자로서 자신을 전달합니다.

의사 코드 : 제외

# a recursive function that is given its previous node, 
# and returns the rightmost node 

recurse_with_previous (tree previous-in): 
    # skip empty link. No leaf to see here! 
    # previous-in is the rightmost node still 
    if null(tree) 
     return previous-in 

    # if we are at a leaf, then that leaf is rightmost 
    if leaf(tree) 
     print "visiting leaf node " tree " with previous node " previous-in 
     return tree 

    # the previous node (previous-in) of this tree is actually the left 
    # subtrees previous node, so we just pass that parameter down 
    previous = recurse_with_previous (left(tree) previous-in) 

    # inorder visit: visit this node between the subtrees 
    print "visiting " tree " with previous node " previous 

    # now the right subtree. what is ITS previous? Why, we are!!! 
    # we return whatever this returns causing the return value 
    # to be the rightmost node. 
    return recurse_with_previous (right(tree) tree) 

# how to call 
recurse_with_previous(some-tree nil) 

Answer 2

(: 그것은 당신이에서 주문 통과를 요구하고 같은 소리지만,보다 더없는 가장 큰 노드를 반환하지 않고 이진 검색 기능하지 않습니다 쿼리).

재귀 알고리즘에서 이와 같은 정보를 추적하는 가장 일반적인 두 가지 방법은 매개 변수로 전달하거나 다시 반환하는 것입니다. (어느 쪽이든 과거에 대한 정보를 스택에 저장하고 있습니다.)

아마도 가장 후자를 수행하는 것이 가장 좋습니다. 예 :

Node* floor_node(int x, Node *subtree) { 
    if (subtree) { 
    if(subtree->value > x) { 
     return floor_node(x, subtree->left); 
    } else { 
     return floor_node(x, subtree->right) || subtree; 
    } 
    } else { 
     return subtree; 
    } 
}