[면접 문제] 이원 찾기 트 리 를 정렬 된 양 방향 링크 로 바 꿉 니 다.

제목: 이원 찾기 트 리 를 입력 하고 이원 찾기 트 리 를 정렬 된 양 방향 링크 로 변환 합 니 다.새로운 노드 를 만 들 수 없고 포인터 의 방향 만 조정 하 라 고 요구 합 니 다.
이원 찾기 트 리
                                            10
                                          /    \
                                        6      14
                                      /  \     /　 \
                                   4     8  12 16
양 방향 링크 로 변환
4=6=8=10=12=14=16。
이원 탐색 트 리 노드 를 정의 하 는 데이터 구 조 는 다음 과 같 습 니 다.
    struct BSTreeNode // a node in the binary search tree     {         int        m_nValue; // value of node         BSTreeNode *m_pLeft; // left child of node         BSTreeNode *m_pRight; // right child of node     };
분석 과 해답: 전체 나 무 를 중간 순서 로 옮 겨 다 닐 수 있 습 니 다. 이 방식 으로 나 무 를 옮 겨 다 니 며 작은 노드 를 먼저 방문 합 니 다. 만약 에 우리 가 하나의 노드 를 방문 할 때마다 이전에 방문 한 노드 가 정렬 양 방향 링크 로 조정 되 었 다 고 가정 하면 현재 노드 를 조정 하 는 지침 을 링크 의 끝 에 연결 합 니 다. 모든 노드 를 방문 한 후에 나무 전체 도 바 꿉 니 다.정렬 양 방향 링크
  코드 는 다음 과 같 습 니 다:

/*         */
void addBSTreeNode(BSTreeNode *&pCurrent,int value)//             ，            
{ 
    if (pCurrent==NULL) 
    { 
        BSTreeNode* pBSTree=new BSTreeNode(); 
        pBSTree->m_nValue=value; 
        pBSTree->m_pLeft=NULL; 
        pBSTree->m_pRight=NULL; 
        pCurrent=pBSTree; 
    } 
    else if (pCurrent->m_nValue<value) 
    { 
        addBSTreeNode(pCurrent->m_pRight,value); 
    } 
    else if (pCurrent->m_nValue>value) 
    { 
        addBSTreeNode(pCurrent->m_pLeft,value); 
    } 
    else
    { 
        cout<<"    "<<endl; 
    } 
 
}
/*                 */
//pNode:    ，         
//pLastNodeInList：            
void convertToDoubleList(BSTreeNode* pNode, BSTreeNode*& pLastNodeInList)
{
         if(pNode == NULL)
            return;
		  BSTreeNode *pCurrent = pNode;
         /*     */
		  if (pCurrent->m_pLeft != NULL)
            convertToDoubleList(pCurrent->m_pLeft, pLastNodeInList);
		   //             
		   pCurrent->m_pLeft = pLastNodeInList;//          
		    
		   if(pLastNodeInList != NULL)
            pLastNodeInList->m_pRight = pCurrent;

            pLastNodeInList=pCurrent;
			//      
         if (pCurrent->m_pRight != NULL)
            convertToDoubleList(pCurrent->m_pRight, pLastNodeInList);
}
//
BSTreeNode* Convert(BSTreeNode* pHeadOfTree)
{
      BSTreeNode *pLastNodeInList = NULL;//         
      convertToDoubleList(pHeadOfTree, pLastNodeInList);
           //           
      BSTreeNode *pHeadOfList = pLastNodeInList;
      while(pHeadOfList && pHeadOfList->m_pLeft)
            pHeadOfList = pHeadOfList->m_pLeft;

      return pHeadOfList; //          

}


int main()
{
	/****       ****/
    BSTreeNode *pRoot=NULL; 
    addBSTreeNode(pRoot,10); 
    addBSTreeNode(pRoot,6); 
    addBSTreeNode(pRoot,14); 
    addBSTreeNode(pRoot,4); 
    addBSTreeNode(pRoot,8); 
    addBSTreeNode(pRoot,12); 
    addBSTreeNode(pRoot,16); 
	/***************       *******************/
 BSTreeNode *pHeadOfList=Convert(pRoot);
/**********************      ******************/
  while(pHeadOfList!=NULL)
	 {
	  cout<<pHeadOfList->m_nValue<<"->";
       pHeadOfList=pHeadOfList->m_pRight;
  }

  return 0;
}