二叉搜索樹與雙向鏈表

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

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

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