제4 8 문제 이 진 검색 수 와 양 방향 링크

제목: 이 진 검색 수의 노드 를 양 방향 링크 형식 으로 변환 합 니 다.
  10   / /  6  14/ / / /4  8 12 16  양 방향 링크 로 전환 4 = 6 = 8 = 10 = 12 = 14 = 16.
우선 우리 가 정의 한 이원 찾기 트 리 노드 의 데이터 구 조 는 다음 과 같다. struct BSTreeNode {  int m_nValue; // value of node   BSTreeNode *m_pLeft; // left child of node   BSTreeNode *m_pRight; // right child of node };

BinaryTreeNode* Convert(BinaryTreeNode* pRootOfTree)
{
    BinaryTreeNode *pLastNodeInList = NULL;
    ConvertNode(pRootOfTree, &pLastNodeInList);

    // pLastNodeInList          ，
    //          
    BinaryTreeNode *pHeadOfList = pLastNodeInList;
    while(pHeadOfList != NULL && pHeadOfList->m_pLeft != NULL)
        pHeadOfList = pHeadOfList->m_pLeft;

    return pHeadOfList;
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList)
{
    if(pNode == NULL)
        return;

    BinaryTreeNode *pCurrent = pNode;

    if (pCurrent->m_pLeft != NULL)
        ConvertNode(pCurrent->m_pLeft, pLastNodeInList);

    pCurrent->m_pLeft = *pLastNodeInList; 
    if(*pLastNodeInList != NULL)
        (*pLastNodeInList)->m_pRight = pCurrent;

    *pLastNodeInList = pCurrent;

    if (pCurrent->m_pRight != NULL)
        ConvertNode(pCurrent->m_pRight, pLastNodeInList);
}