비 재 귀적 으로 이 진 트 리 의 뒷 순 서 를 찾 습 니 다.

1571 단어 데이터 구조
알고리즘 설명:
단계 1:
             현재 노드 부터 현재 노드 와 그의 왼쪽 서브 트 리 의 모든 왼쪽 노드 를 스 택 에 들 어가 처리 하지만 스 택 에 들 어 가 는 과정 에서 방문 하지 않 고 현재 노드 의 가장 왼쪽 잎 노드 까지 합 니 다.
단계 2:
            스 택 에 들 어가 자마자 스 택 을 나 가기 시작 합 니 다. 스 택 을 나 가기 전에 스 택 꼭대기 요소 에 오른쪽 하위 트 리 가 있 는 지 판단 합 니 다. 오른쪽 하위 트 리 가 없 으 면 스 택 을 나 와 이 노드 를 방문 하고 현재 방문 한 노드 주소 정 보 를 포인터 로 기록 합 니 다. 스 택 꼭대기 요소 가 오른쪽 하위 트 리 가 있 을 때 까지 합 니 다.
단계 3:
            스 택 꼭대기 요소 가 오른쪽 하위 트 리 가 있 을 때 지난번 에 방문 한 위치 가 스 택 꼭대기 요소 의 오른쪽 노드 인지 판단 해 야 합 니 다. 만약 에 그렇다면 스 택 처 리 를 계속 하고 현재 방문 한 노드 주소 정 보 를 기록 해 야 합 니 다. 스 택 꼭대기 요소 가 오른쪽 하위 트 리 가 있 고 지난번 에 방문 한 노드 가 스 택 꼭대기 요소 의 오른쪽 노드 가 아 닐 때 까지 기록 해 야 합 니 다.
단계 4: 스 택 꼭대기 요소 가 오른쪽 하위 트 리 가 있 고 지난번 에 방문 한 노드 가 스 택 꼭대기 요소 의 오른쪽 노드 가 아니면 스 택 꼭대기 요소 의 오른쪽 노드 를 절차 처음부터 다시 실행 합 니 다. 스 택 이 비어 있 을 때 까지.
 
 
struct bstree_record;
typedef struct bstree_record* bstree;
struct bstree_record
{
  int data;
  bstree m_pleft;
  bstree m_pright;
};

void  post_visit(bstree t)
{
  if(t)
  {
        bstree prev = NULL;
        bstree cur = t;
        stack s = NULL;
        while(cur)
        {
            while(cur)
           {
              PushStack(cur,s);
              cur = cur->m_pleft;
           }
  
           cur = TopStack(s);
           while(cur && (cur->m_pright == NULL || cur->m_pright == pre)
           {
               printf(“the data is %d”,cur->data);
               prev = cur;
               PopStack(s);
               cur = TopStack(s);
           }
`	}
  }
}

좋은 웹페이지 즐겨찾기