재귀 (스택 사용)가 아닌 비 이진 트리를 통과하는 알고리즘은 무엇입니까

Question

직관적으로 나는 (node, iterator)과 같은 스택 쌍을 계속 이해하지만 여전히 해결 방법을 찾을 수 없습니다.

Answer 1

항상 재귀 알고리즘을 명시 적 스택이있는 알고리즘으로 변환 할 수 있습니다. 재귀 코드로 시작

void traverse(NODE *p) { 
    if (p) { 
    for (int i = 0; i < p->n_children; ++i) { 
     traverse(p->child[i]); 
    } 
    } 
} 

은 재귀 호출을 대체 :이

struct { 
    NODE *p; 
    int i; 
} stk[MAX_RECURSION_DEPTH]; 
int sp = 0; 

void traverse(NODE *p) { 
start: 
    if (p) { 
    for (int i = 0; i < p->n_children; ++i) { 
     // Save local values on stack. 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     // Simulate recursive call. 
     p = p->child[i];   
     goto start; 
     // Goto this label for return. 
    rtn: 
    } 
    } 
    // Simulate recursive return, restoring from stack if not empty. 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    goto rtn; 
} 

당신은 그것을 가지고 :이 명시 적 스택 구현 한 재귀 버전처럼 작동 할 수 있습니다. 그건 같은거야.

이제 원하는 경우 goto을 제거하기위한 대수를 수행합니다. 먼저 우리는 while로 for를 다시 작성하고 rtn 라벨에게 while 내부의 ++i 죽은 코드를했다

void traverse(NODE *p) { 
    int i; 
start: 
    if (p) { 
    i = 0; 
    rtn_2: 
    while (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    ++i; 
    goto rtn_2; 
} 

참고 리팩토링, 너무 떨어 안전하다고 할 수 있습니다.

while의 본문이 두 번 이상 실행되지 않습니다. if으로 대체 할 수 있습니다. goto rtn_2을 실행 코드로 바꿀 수도 있습니다.

void traverse(NODE *p) { 
    int i; 
start: 
    if (p) { 
    i = 0; 
    if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
    for (;;) { 
    if (sp == 0) return; 
    p = stk[--sp].p; 
    i = stk[sp].i; 
    ++i; 
    if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     goto start; 
    } 
    } 
} 

마지막으로, 우리는 대신 루프를 사용하여 start 라벨을 제거 할 수 있습니다

void traverse(NODE *p) { 
    int i; 
    for (;;) { 
    if (p) { 
     i = 0; 
     if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     continue; 
     } 
    } 
    for (;;) { 
     if (sp == 0) return; 
     p = stk[--sp].p; 
     i = stk[sp].i; 
     ++i; 
     if (i < p->n_children) { 
     stk[sp].p = p; 
     stk[sp++].i = i; 
     p = p->child[i];   
     break; 
     } 
    } 
    } 
} 

또 다른 정리 i은 항상 첫 번째 if 0이므로주의하는 것입니다, 그리고 continue은 실제로 우리가 명시 적으로 만들 수있는 중첩 루프를 구현합니다. 삭제 될 수있는 중복 stk[sp].p = p;도 있습니다.

void traverse(NODE *p) { 
    for (;;) { 
    while (p && p->n_children > 0) { 
     stk[sp].p = p; 
     stk[sp++].i = 0; 
     p = p->child[0];   
    } 
    for (;;) { 
     if (sp == 0) return; 
     p = stk[--sp].p; 
     int i = stk[sp].i + 1; 
     if (i < p->n_children) { 
     stk[sp++].i = i; // stk[sp].p = p; was redundant, so deleted 
     p = p->child[i];   
     break; 
     } 
    } 
    } 
} 

그것은 코드가 조금 더 예쁘게 만들 수 있어요,하지만 난 당신을 떠날 것이다 : 단지 이미 거기에 스택에 값을 복사합니다. 주목할 점은 포인터가 무엇을하고 있는지 상상력이나 상상력이 없다는 것입니다. 우리는 코드에 대해 대수를 수행했고 합리적으로 좋은 구현이 이루어졌습니다. 나는 그것을 실행하지 않았다. 그러나 내가 가능한 대수 실수를하지 않았다면, 이것은 "그냥 일해야한다".

이것은 교과서에서 볼 수있는 일반적인 스택 기반 DFS와는 조금 다릅니다. 이들은 스택에서 새로 발견 된 노드의 모든 자식을 푸시합니다. 정상적인 DFS 순서를 얻으려면 맨 오른쪽 자식에서 먼저 수행해야합니다.

대신에 우리는 어떤 아이가 다음에 검색되어야 하는지를 나타내는 정수와 함께 부모를 밀고 있습니다. 이것은 당신이 언급 한 노드 + 반복자입니다. 조금 더 복잡하지만 스택 크기가 더 효율적입니다. 스택의 최대 크기는 O (D)입니다. 여기서 D는 트리의 최대 깊이입니다. 교과서 알고리즘의 스택 크기는 O (KD)입니다. 여기서 K는 노드가 가질 수있는 최대 자식 수입니다.