세 가지 이 진 트 리 가 옮 겨 다 니 는 비 재 귀적 실현

오늘 우연히 오래전 에 쓴 블 로 그 를 꺼 냈 습 니 다. 세 가지 이 진 트 리 가 옮 겨 다 니 는 비 재 귀적 실현 에 관 한 것 입 니 다. 여기 로 넘 어 오 세 요.프로그램 은 모두 위조 코드 이다. 대학원 복습 기간 에 쓴 것 이기 때문에 데이터 구 조 는 엄 울 민의 을 참고 했다.
먼저 재 귀 실현 을 본다.

void Traverse(BiTree T){
    if(T){
    //visit,    
    Traverse(T->lchild);
    //visit,    
    Traverse(T->rchild);
    //visit,    
    }
}

세 가지 스 트 리밍 방법의 재 귀 실현 형식 이 똑 같 고 visit 의 위 치 를 바 꾸 면 서로 다른 스 트 리밍 순 서 를 얻 을 수 있 습 니 다.따라서 감정 적 으로 비 재 귀적 실현 은 형식 도 똑 같 아야 한다 고 생각한다. 이것 은 교과서 가 준 중 서 비 재 귀적 실현 이다.

void InOrderTraverse（BiTree T, status(* visit)(TElemType e)）{
    InitStack(s); p=T;
    while(p || !StackEmpty(s)){
        if(p){
        Push(s,p); p=p->lchild;
        }else{
        Pop(s,p);visit(p->data);p=p->rchild;
        }
    }
}

visit (p - > data) 만 사용 하기;Push (s, p) 로 이동 하기;그 후에 선착순 으로 옮 겨 다 니 는 비 재 귀적 실현 을 얻 을 수 있다.그 다음 에 뒷 순 서 를 고려 할 때 이런 형식 은 뒷 순 서 를 옮 겨 다 니 지 않 기 때문에 나중에 스스로 뒷 순 서 를 옮 겨 다 니 는 비 재 귀 프로그램 을 써 야 했다.그러나 마음 이 불편 하 다. 왜 재 귀 실현 에 있어 서 이렇게 통일 되 었 고 비 재 귀 실현 에 이 르 러 서 야 순서 가 남 달 라 졌 을 까?복습 시간 이 매우 긴 장 돼 서 이 문제 에 대해 서 는 기본적으로 뿔뿔이 흩 어 져 있 습 니 다. 걸 을 때 쭈 그리고 앉 아 있 고 심심 할 때 는 끝 없 이 이상 한 생각 을 합 니 다. 어느 날 쭈 그리고 앉 았 을 때 까지 생각 했 습 니 다.
교과서 의 비 재 귀적 실현 은 스 택 에 대한 사용 이 재 귀적 스 택 과 같 지 않 기 때문에 결산 점 의 출입 스 택 순서 도 재 귀적 스 택 과 현저히 다르다. 이 를 바탕 으로 재 귀적 스 택 작업 의 비 재 귀적 실현 을 완전히 모방 했다. 관건 은 스 택 에서 나 오 는 조건 에 변화 가 생 겼 다 는 것 이다. 그리고 직관 적 으로 이 프로그램의 스 택 과 스 택 에 들 어 가 는 문구 (Push, Pop) 는 왼쪽 아이 와 오른쪽 아 이 를 부여 하 는 것 이다.(p = p - > lchild 또는 rchild) 는 한 번 만 나타 나 야 합 니 다. 여러 번 나타 나 면 기능 이 중복 되 었 을 것 입 니 다. 다시 줄 일 수 있 습 니 다.

status Traverse(BiTree T, status(* visit)(TElemType e)){
    IniTStack(s); p=T; p1=NULL;
    while(p || !StackEmpty(s)){
        if(p){
            Push(s,p);
            //visit,  
            p=p->lchild;
        }else{
            GetTop(s,p);
            //visit,  
            if(p->rchild==p1 || p->rchild==NULL){
                Pop(s,p1);p=NULL;
                //visit,  
            }else{
                p=p->rchild;p1=NULL;
            }
        }
    }
}

이런 형식 에서 visit 의 위 치 를 바 꾸 기만 하면 세 가지 비 재 귀 실현 을 얻 을 수 있 습 니 다. 결산 점 의 출입 순 서 는 재 귀 스 택 과 마찬가지 로 결산 점 이 스 택 에서 나 오 는 지 여 부 를 판단 하 는 조건 은 지난번 에 스 택 에서 나 온 결산 점 은 스 택 꼭대기 요소 의 오른쪽 아이 입 니 다.
이 진 트 리 몇 그루 를 시험 한 결과 맞 았 지만 소홀 한 점 이 있 는 지 는 알 수 없 었 다.