이진 검색 트리 중위 순회

Question

는이 코드에 의해 혼란 스러워요 :

void in_order_traversal_iterative(BinaryTree *root) { 
    stack<BinaryTree*> s; 
    BinaryTree *current = root; 
    while (!s.empty() || current) { 
    if (current) { 
     s.push(current); 
     current = current->left; 
    } else { 
     current = s.top(); 
     s.pop(); 
     cout << current->data << " "; 
     current = current->right; 
    } 
    } 
} 

우리는 루트를 가리 키도록 포인터를 설정합니다. 그런 다음 존재한다면, 현재 (루트 인) 현재 스택으로 밀어 넣으십시오. 노드가 보유하고있는 데이터의 가치가 아니라 전체 트리를 초기에 스택으로 밀어 넣는 이유는 알 수 없습니다. 내가 완전히 무언가를 놓치고 있거나 그것이 왜 이렇게 효과가 있을지 이해하지 못하고 있습니까? 왜 우리가 하나의 노드가 아닌 전체 트리를 밀어 넣는 지 이해할 수 없습니다 ...

Answer 1

당신은 노드가 터진 후, 오른쪽 아이가 여전히 통과해야한다는 사실이 누락

: 당신은 스택에 데이터 만 가지고 있다면

current = s.top(); 
    s.pop(); 
    cout << current->data << " "; 
    current = current->right; 

을이 불가능하다. 루프 불변량은 스택이 우회되지 않은 오른쪽 자식이있는 노드를 정확하게 보유한다는 것입니다.

무슨 일이 일어나고 있는지 볼 수있는 또 다른 방법은 대수에 의해 반복적으로 재귀 순회를 변환하는 것입니다

traverse(node) { 
    if (node) { 
    traverse(node->left); 
    visit(node); 
    traverse(node->right); 
    } 
} 

먼저 반복에 꼬리 호출을 변환합니다. 우리는 함수의 시작 인수를 업데이트하고 goto로 재귀 호출을 대체하여이 작업을 수행 :

traverse(node) { 
start: 
    if (node) { 
    traverse(node->left); 
    visit(node); 
    node = node->right; 
    goto start; 
    } 
} 

goto 및 if가 while과 동일을, 그래서 우리는 지금까지

traverse(node) { 
    while (node) { 
    traverse(node->left); 
    visit(node); 
    node = node->right; 
    } 
} 

이

다른 재귀 호출을 대체하려면 컴파일러 런타임 환경의 호출 스택을 시뮬레이트해야합니다. 우리는 명시 적 스택을 사용하여이를 수행합니다.

traverse(node) { 
start: 
    while (node) { 
    stack.push(node); // save the value of the argument. 
    node = node->left; // redefine it the same way the recursive call would have 
    goto start;   // simulate the recursive call 
         // recursive call was here; it's gone now! 
    recursive_return: // branch here to simulate return from recursive call 
    visit(node); 
    node = node->right; 
    } 
    // simulate the recursive return: if stack has args, restore and go to return site 
    if (!stack.empty()) { 
    node = stack.pop(); // restore the saved parameter value 
    goto recursive_return; 
    } 
} 

이것은 추악하지만 재귀 코드의 반복 버전을 구현하는 방식입니다. (꼬리가 아닌 재귀 호출이 여러 개있는 경우에는 더 복잡합니다.) 그리고 코드와의 유사성을 확인할 수있을 것입니다.

우리는 심지어 더 많은 대수를 사용하여 추함을 없앨 수 있습니다. start로 시작하는 실행

while (node) { 
    stack.push(node); // save the value of the argument. 
    node = node->left; // redefine it the same way the recursive call would have 
    } 

에 해당하는 경우

start: 
    while (node) { 
    stack.push(node); // save the value of the argument. 
    node = node->left; // redefine it the same way the recursive call would have 
    goto start;   // simulate the recursive call 

이

우리는 또한 다음과 같은

if (!stack.empty()) { 
    node = stack.pop(); // restore the saved parameter value 
    visit(node); 
    node = node->right; 
    goto start; 
    } 

와

if (!stack.empty()) { 
    node = stack.pop(); // restore the saved parameter value 
    goto recursive_return; 
    } 

을 대체 할 수있다 : 첫째,이 코드를 볼 어렵지 않다

recursive_return: 다음의 세 명령을 if 본문에 복사했습니다.이와

는 방법이 recursive_return 라벨에 도착 남아 있지, 그래서 우리는 다음 두 문장과 함께 삭제할 수 있습니다 :

// Dead code! Delete me! 
    recursive_return: 
    visit(node); 
    node = node->right; 

우리는 지금이 :

traverse(node) { 
start: 
    while (node) { 
    stack.push(node); // save the value of the argument. 
    node = node->left; // redefine it the same way the recursive call would have 
    } 
    if (!stack.empty()) { 
    node = stack.pop(); // restore the saved parameter value 
    visit(node); 
    node = node->right; 
    goto start; 
    } 
} 

우리는 무한 루프로 교체하여 마지막 goto start을 제거 할 수 있습니다.

이전 코드와 동일한 조건에서 반환됩니다. 스택이 비어 있습니다!

이 코드는 사용자가 제시 한 코드와 동일하다는 것을 증명할 것입니다. 일부 비교를 피하기 때문에 좀 더 효율적입니다. 우리는 포인터와 스택 요소에 대해 전혀 추론 할 필요가 없었습니다. 그것은 "그냥 일어났다."

Answer 2

전체 트리를 스택으로 밀어 넣지 않고 트리의 가장 왼쪽 부분을 푸시합니다. 그런 다음 요소를 팝핑하고 가장 오른쪽에있는 요소를 오름차순으로 밀어 내기 시작합니다.