二叉搜索樹與雙向鏈表

題目:輸入一棵二叉搜索樹，現在要將該二叉搜索樹轉換成一個排序的雙向鏈表。而且在轉換的過程中，不能創建任何新的結點，只能調整樹中的結點指針的指向來實現。

思路：采用中序遍歷將二叉樹從小到大遍歷每一個結點，通過改變指針來實現雙向鏈表。

#include<stdio.h>
#include "stdafx.h"
#include<tchar.h>

struct BinaryTreeNode
{
    int              m_nValue;
    BinaryTreeNode*  m_pLeft;
    BinaryTreeNode*  m_pRight;
};
BinaryTreeNode* CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;
}
void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}
void PrintTreeNode(BinaryTreeNode* pNode)
{
    if(pNode != NULL)
    {
        printf("value of this node is: %d\n", pNode->m_nValue);
       
        if(pNode->m_pLeft != NULL)
            printf("value of its left child is: %d.\n", pNode->m_pLeft->m_nValue);
        else
            printf("left child is null.\n");
       
        if(pNode->m_pRight != NULL)
            printf("value of its right child is: %d.\n",pNode->m_pRight->m_nValue);
        else
            printf("right child is null.\n");
    }
    else
    {
        printf("this node is null.\n");
    }
    printf("\n");
}
void PrintTree(BinaryTreeNode* pRoot)
{
    PrintTreeNode(pRoot);
   
    if(pRoot != NULL)
    {
        if(pRoot->m_pLeft != NULL)
            PrintTree(pRoot->m_pLeft);
       
        if(pRoot->m_pRight != NULL)
            PrintTree(pRoot->m_pRight);
    }
}
void DestroyTree(BinaryTreeNode* pRoot)
{
    if(pRoot != NULL)
    {
        BinaryTreeNode* pLeft = pRoot->m_pLeft;
        BinaryTreeNode* pRight = pRoot->m_pRight;
       
        delete pRoot;
        pRoot = NULL;
       
        DestroyTree(pLeft);
        DestroyTree(pRight);
    }
}

void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList);

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);
}

//打印雙向鏈表
void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList)
{
    BinaryTreeNode* pNode = pHeadOfList;
   
    printf("The nodes from left to right are:\n");
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);
       
        if(pNode->m_pRight == NULL)
            break;
        pNode = pNode->m_pRight;
    }
    printf("\n");
}

void DestroyList(BinaryTreeNode* pHeadOfList)
{
    BinaryTreeNode* pNode = pHeadOfList;
    while(pNode != NULL)
    {
        BinaryTreeNode* pNext = pNode->m_pRight;
       
        delete pNode;
        pNode = pNext;
    }
}

//            10
//        /      \
//        6        14
//      /\        /\
//      4  8    12  16

int main()
{
    BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);
    BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);
    BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);
    BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);
    BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);
    BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);
    BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);
   
    ConnectTreeNodes(pNode10, pNode6, pNode14);
    ConnectTreeNodes(pNode6, pNode4, pNode8);
    ConnectTreeNodes(pNode14, pNode12, pNode16);
   
    PrintTree(pNode10);
   
    BinaryTreeNode* pHeadOfList = Convert(pNode10);
   
    printf("The nodes from left to right are:\n");
    PrintDoubleLinkedList(pHeadOfList);
    printf("\n");
   
    DestroyList(pNode4);
}