二叉搜索树与双向链表

题目:输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。而且在转换的过程中，不能创建任何新的结点，只能调整树中的结点指针的指向来实现。

思路：采用中序遍历将二叉树从小到大遍历每一个结点，通过改变指针来实现双向链表。

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