이원 탐색 트 리 를 정렬 된 양 방향 링크 로 바 꾸 는 알고리즘 사고

제목: 이원 찾기 트 리 를 정렬 된 양 방향 링크 로 바 꾸 고 새로운 노드 를 만 들 지 말고 포인터 의 방향 만 조정 하 라 고 요구 합 니 다.원제 및 원 해답 은 JULY 의 블 로그 '구조의 법 알고리즘 도' 의 마이크로소프트 면접 100 문제 2010 년 판 전체 답안 집 (다운로드 주소 포함) 을 보십시오.
처음에 이 문 제 를 보고 생각 이 복잡 하 다 고 생각 한 후에 반성 하기 시작 했다.
1. 이것 은 나무 에 관 한 문제 입 니 다. 일반적으로 재 귀 알고리즘 과 나무의 역 사 를 검사 합 니 다.
2. 이것 은 이원 에서 나 무 를 찾 는 것 입 니 다. 그러면 어 릴 때 부터 큰 순 서 는 나무의 앞 순 서 를 목록 에 옮 겨 다 니 는 것 입 니 다. 다시 말 하면 문제 가 우리 에 게 결점 을 다시 만 들 수 있 도록 허락 한다 면 앞 순 서 를 통 해 차례대로 결점 을 만 들 면 자 연 스 럽 게 해결 할 수 있 습 니 다.
3. 그러나 제목 은 새로운 결점 을 만 들 수 없다. 다시 생각해 보면 결점 을 만 들 필요 가 없다. 앞 순 서 를 옮 겨 다 닐 때 우리 가 현재 결점 을 방문 할 때 앞의 결점 을 얻 을 수 있다 면 자 연 스 럽 게 연결 할 수 있다.
이 사고방식 이 형 성 된 후에 다음 과 같은 코드 가 형성 되 었 다.

/*    ，            */
BSTreeNoe * changeTreeToLinkList ( BSTreeNode *Tree ) {
  BSTreeNode *former=NULL,  *head=Tree;
  if ( ! Tree) return NULL;
  InOrderTraverse ( Tree, former );
  while ( head->m_pLeft != NULL )  head=head->m_pLeft;
  return head;
}

/*    */
void InOrderTraverse ( BSTreeNode *Tree, BSTreeNode * &former) {
  if ( Tree->m_pLeft )  InOrderTraverse ( Tree->m_pLeft, former );
  visit ( Tree, former );
  if ( Tree->m_pRight)  InOrderTraverse ( Tree->m_pRight, former );
}

/*    ，  former  ，                  */
void visit ( BSTreeNode *Tree, BSTreeNode * &former) {
  if ( former==NULL ) {
    former=Tree;
  }else{
    former->m_pRight=Tree;
    Tree->m_pLeft=former;
    former=Tree;
  } 
}

이렇게 해서 첫 번 째 해법 이 형성 되 었 다.이어서 두 번 째 해법 이 있 는 지 생각 하기 시작 했다.이것 은 나무 에 관 한 문제 로 일반적으로 규칙 을 찾 아 나무 결점 과 좌우 자수의 각도 에서 생각해 야 한다.
1. 결점 A 에 왼쪽 나무 가 있다 면 A 의 앞 구 조 는 왼쪽 나무의 가장 큰 결점 이 고 A 나무의 가장 작은 결점 은 왼쪽 나무의 가장 작은 결점 이다.2. 만약 에 결점 A 가 왼쪽 나무 가 없다 면 A 는 반드시 특정한 결점 의 선구자 일 것 이다.그리고 A 나무의 가장 작은 결점 은 A 이다.3. 만약 에 결점 A 에 오른쪽 나무 가 있다 면 A 의 후계 점 은 오른쪽 나무의 가장 작은 결점 이 고 A 나무의 가장 큰 결점 은 오른쪽 나무의 가장 큰 결점 이다.4. 만약 에 결점 A 가 오른쪽 나무 가 없다 면 A 는 반드시 특정한 결점 의 후계 이 고 A 나무의 가장 큰 결점 은 A 이다.이해 하기 에는 스트레스 가 많 습 니 다........................................................................................