二叉搜索树与双向链表

/**************************************************
输入一颗二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的节点，只能调整树中节点指针的指向。
***************************************************/
#include<stdio.h>

struct BinaryTreeNode
{
	int m_nValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};

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("\nThe nodes from right to left are:\n");
    while(pNode != NULL)
    {
        printf("%d\t", pNode->m_nValue);

        if(pNode->m_pLeft == NULL)
            break;
        pNode = pNode->m_pLeft;
    }

    printf("\n");
}

BinaryTreeNode* CreateBinaryTreeNode(int value)
{
    BinaryTreeNode* pNode = new BinaryTreeNode();
    pNode->m_nValue = value;
    pNode->m_pLeft = NULL;
    pNode->m_pRight = NULL;

    return pNode;
}

void ConnectTreeNodes(BinaryTreeNode* pParent, BinaryTreeNode* pLeft, BinaryTreeNode* pRight)
{
    if(pParent != NULL)
    {
        pParent->m_pLeft = pLeft;
        pParent->m_pRight = pRight;
    }
}

void convertNode(BinaryTreeNode* pNode,BinaryTreeNode** pLastNodeInList);
BinaryTreeNode* convertBSTtoBinaryList(BinaryTreeNode* pRoot)
{
	BinaryTreeNode* pLastNodeInList = NULL;	//指向已经转换好的链表的最后一个节点(也是最大值)
	convertNode(pRoot,&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 test()
{
    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);

	BinaryTreeNode* pHeadOfList = convertBSTtoBinaryList(pNode10);
	PrintDoubleLinkedList(pHeadOfList);
}
int main()
{
	test();
	return 0;
}

根节点、左子树和右子树。在把左子树、右子树都转换成排序的双向链表之后再和根节点连接起来，整棵二叉搜索树也就转换成了排序的双向链表。

参考剑指offer