데이터 구조_지식 포인트_두 갈래 나무가 두루 다니다

흔히 볼 수 있는 역행 방식은 네 가지가 있는데, 선순, 중순, 후순, 차원 역행이다.

1. 선중후순 반복(귀속)

void preOrder(tree t)
{
    if(t != NULL)
    {
        visit(t);
        preOrder(t->lchild);
        preOrder(t->rchild);
    }
}

선중, 후,visit의 순서를 조정했을 뿐이다.

2. 선중순 반복(비귀속)

void InOrder2(tree t)
{
    InitStack(s);
    tree p = t;
    
    while(!p || !IsEmpty(s))
    {
        if(p)
        {
            push(s,p);
            p = p->lchild;
        }
        else
        {
            pop(s,p);
            visit(p);
            p = p->rchlid;
        }
    }
}

앞 순서든 중간 순서든 결점 포인터의 순서는

뿌리 결점을 가리키며 창고에 들어간다

끊임없이 왼쪽 아이를 가리키며 창고에 들어간다(이때 결점을 방문하고 앞순서)

비울 때까지

창고를 통과하는 결점을 가리키고 양친을 가리킨다(이때 결점을 방문하고 중서)

오른쪽 아이를 가리킨다

상술한 과정을 끊임없이 반복하여 두 갈래 나무의 오른쪽 자목 최하층의 가장 오른쪽 결점을 가리킬 때까지 한다. 이때 양친을 가리키지 않기 때문에 임시로 양친 결점을 보존하는 창고는 이미 비어 있다.다시 이 결점의 오른쪽 아이(창고는 여전히 비어 있음)를 가리키면 오른쪽 아이도 비어 있기 때문에 퇴출 순환을 만족시킨다.
미시적으로 볼 때 포인터가 한 결점을 가리키는데 왼쪽 아이(왼쪽 아이가 비어 있지 않을 때 방문해야 함)에 접근하려면 이 결점을 저장하여 오른쪽 아이에 접근하기 위해 포인터가 결점을 가리키도록 해야 한다
모든 지점은 먼저 양친 결점을 가리키고 그 왼쪽 아이를 가리키며 (왼쪽 나무를 두루 돌아다닐 수도 있다) 그 다음에 뒤돌아서서 양친 결점을 가리키고 그 오른쪽 아이를 가리킨다(오른쪽 나무를 두루 돌아다닐 수도 있다)
전순, 중순의 차이는 전순이 처음 결점을 가리킬 때, 방문 결점 중순은 바늘이 결점을 가리키는 왼쪽 아이, 창고를 통해 바늘이 다시 결점을 가리킬 때, 방문 결점

3. 후순 비귀속

후면 반복 방식은 여전히 창고를 사용하고 분석할 수 있는 반복 절차는 다음과 같다.

I.  ， 
II.  ， 
III.  ，  
IV.  ， 
V.  

입적 규칙: 결점 입적, 왼쪽 자수 입적, 모든 왼쪽 자수 출적 후, 결점 오른쪽 자수 입적.출고 규칙: 결점은 잎 노드로 즉시 출고;결점의 좌우 아이들은 모두 방문한 적이 있다.
한 개의 하위 나무의 뿌리 결점은 이 과정에서 모두 세 번의 지침에 의해 가리킨 적이 있다. 첫 번째는 왼쪽 아이를 방문하고, 두 번째는 오른쪽 아이를 방문하고, 마지막 번째는 이 결점을 방문한다.
어떻게 판단하는가가 몇 번째 지향 결점으로 어떻게 조작해야 하는지를 확정하는 것이 문제의 관건이다.방법은 두 가지가 있다. (1) 지난번 창고 결점을 가리키는 바늘을 보존한다. 만약에 창고 꼭대기 결점의 왼쪽 아이와 같다면 왼쪽 나무가 반복적으로 완성된 것을 나타낸다. 오른쪽 나무가 창고 꼭대기 결점의 오른쪽 아이와 같다면 현재 결점의 좌우 나무가 모두 반복된 것을 나타낸다. 창고가 모두 아니라면 바늘이 창고 꼭대기 왼쪽 아이를 가리키고 창고에 들어갈 수 있다.
(2) tag 창고를 만들고 s 창고의 결점이 방문한 횟수를 기록합니다. 매번 창고 꼭대기 결점만 처리합니다.뿌리 결점이 창고에 들어갑니다. tag가 0이면 왼쪽 트리를 훑어보기 시작하고 tag++tag가 1이면 오른쪽 트리를 훑어보기 시작하며 tag++tag가 2이면 왼쪽 트리를 훑어보고 결점과 tag를 창고에서 내보냅니다.

void traverse(tree t)
{
    initStack(s);
    initStack(tag);
    
    tree p = t;
    push(p,s);
    push(0,tag);

    while(!IsEmpty(s))
    {
        switch(tag[top])
        {
            case 0:
                {
                    tag[top]++;
                    p = getTop(s)->lchild;

                    if(p)
                    {
                        push(p,s);
                        push(0,tag);
                    }    
                }
            case 1:
                {
                    tag[top]++;
                    p = getTop(s)->rchild;

                    if(p)
                    {
                        push(p,s);
                        push(0,tag);
                    }    
                    
                }
            case 2:
                {
                    visit(s[top]);
                    pop(s);
                    pop(tag);
                }
        }

    }
}

(3) 더블 스택법

뿌리 결점 진입 s1

뿌리 결점 출점, s2 진입

뿌리 결점의 왼쪽 결점은 s1에 들어가고 오른쪽 결점은 s1에 들어간다

우결점 출점, s2 진입

왼쪽 결점 출점, s2에 들어가기 때문에 s2에 들어가는 순서는 뿌리 결점, 오른쪽 결점, 왼쪽 결점 출점의 순서, 왼쪽 결점, 오른쪽 결점, 뿌리 결점이다

void PostTraverse(BiTree T){  
    BiTree root = T ;  
    SqStack S1,S2; // ，S1 ，S2   
      
    //   
    InitStack(S1);   
    InitStack(S2) ;  
  
    Push(S1,root);  //1.   
  
    while(!isEmpty(S1)){ // S1 ：1. S1  2. S1 S2  
          
            BiTree P=Pop(S1);  
            Push(S2,P);  
            if(P->lchild !=NULL) Push(S1,P->lchild);  
            if(P->rchild !=NULL) Push(S1,P->rchild) ;  
    }  
    while(!isEmpty(S2)){  
        printf("%c",(*(--S2.top))->data);  
    }  
}