바이너리 tree_javascript 기술에 대한 비재귀적 후순 순회 알고리즘의 자세한 예

pre-order, mid-order 및 post-order의 비재귀 순회 중에서 post-order가 가장 문제가 되는 것은 스택의 노드에 대한 포인터만 유지하는 경우 일부 추가 정보로는 충분하지 않습니다. 스택 중간에 저장됩니다.
여러 가지 방법이 있지만 여기서는 단 하나의 방법만 사용합니다. 먼저 스택 노드의 데이터 구조를 정의합니다

코드 복사 코드는 다음과 같습니다.

typedef struct{Node * p int rvisited; ;}SNode //Node는 이진 트리의 노드 구조입니다. rvisited==1은 p가 가리키는 노드의 오른쪽 노드를 방문했음을 의미합니다.

lastOrderTraverse(BiTree bt){
　 //먼저 루트 노드부터 시작하여 왼쪽 아래로 이동하여 끝까지 이동하여 경로에 있는 모든 노드를 스택에 푸시합니다.
p = bt; 통과
　bt = bt.lchild;
　}

//그리고 루프에 들어갑니다.

while(!Stack.empty()){ //스택이 비어 있지 않은 한

sn = Stack.getTop() // sn이 최상위 노드입니다. 스택

　 //N 노드에 왼쪽 자식이 있는 한 N이 스택에 푸시된 후 N의 왼쪽 자식도 스택에 푸시되어야 합니다(이는 알고리즘의 후반부에 반영됩니다). 스택의 맨 위에 있는 요소를 얻을 때 이 요소에 왼쪽 자식이 없거나 왼쪽 자식이 방문되었음을 확신할 수 있으므로 현재로서는 왼쪽 자식에 대해 신경 쓰지 않습니다. 오른쪽 아이에게만 관심이 있습니다.

　　 //오른쪽 자식을 방문했거나 요소에 오른쪽 자식이 없으면 후위 순회 정의에 따라 이때 이 노드를 방문할 수 있습니다.

　if(!sn.p.rchild || sn.rvisited){

　　p = pop();
　　visit(p);
　　}
　　else //올바른 자식인 경우 It 존재하고 rvisited는 0입니다. 이는 오른쪽 자식이 이전에 터치된 적이 없으므로 오른쪽 자식을 처리한다는 의미입니다.
　　{
　　　 //이때 오른쪽 자식 노드부터 시작하여 끝에 도달할 때까지 왼쪽 아래까지 계속 이동하고 이 경로의 모든 노드를 스택에 푸시해야 합니다.

　　　 //물론 노드를 스택에 푸시하기 전에 노드의 rvisited를 1로 설정해야 합니다. 왜냐하면 오른쪽 자식을 스택에 푸시한다는 것은 오른쪽 자식을 먼저 방문한다는 의미이기 때문입니다(이것은 이해하기 쉽습니다. 우리는 방문을 위해 항상 스택의 맨 위에서 요소를 가져오기 때문입니다. 다음에 요소가 스택 맨 위에 있을 때 오른쪽 자식을 방문해야 하므로 여기서 rvisited를 1로 설정할 수 있음을 알 수 있습니다.

sn.rvisited = 1

// 왼쪽 하단으로 이동하여 경로에 있는 모든 요소를 ​​스택에 푸시합니다.

p = sn.p.rchild;

while(p != 0){
push(p, 0 ) ;
　　　　p = p.lchild;
　　　}
　　}//이번 루프는 종료되었습니다. 방금 스택에 푸시된 노드에 대해 걱정할 필요가 없습니다. 이 노드를 잘 관리하세요.
　}
}