分析:
1. 二叉树中,每个结点都有两个指向子结点的指针。
2. 在双向链表中,每个结点也有两个指针,分别指向前一个结点和后一个结点。
3. 二叉搜索树中,左子结点的值总是小于父结点的值,右子结点的值总是大于父结点的值。
4. 将二叉搜索树转换为双向链表时,原先指向左子结点的指针调整为链表中指向前一个结点的指针,原先指向右子结点的指针调整为链表中指向后一个结点的指针。
5. 由于要求转换之后的链表是排好序的,所以我们采取中序遍历。
6. 当遍历转换到根结点时,左子树已经转换成了一个排序的链表了,并且处在链表中的最后一个结点是当前值最大的结点,将其与根结点连接起来,接着去遍历转换右子树,并把根结点和右子树中的最小的结点连接起来。
代码:
#include "stdafx.h" #include <iostream> using namespace std; struct BinaryTreeNode { int m_nValue; BinaryTreeNode *m_pLeft; BinaryTreeNode *m_pRight; }; void Convert(BinaryTreeNode *pRoot, BinaryTreeNode *&pLastInList) { if (pRoot == NULL) { return; } BinaryTreeNode *pCurrentNode = pRoot; if (pCurrentNode->m_pLeft != NULL) { Convert(pCurrentNode->m_pLeft, pLastInList); } pCurrentNode->m_pLeft = pLastInList; if (pLastInList != NULL) { pLastInList->m_pRight = pCurrentNode; } pLastInList = pCurrentNode; if (pCurrentNode->m_pRight != NULL) { Convert(pCurrentNode->m_pRight, pLastInList); } } BinaryTreeNode *ConvertBSTToDoubleList(BinaryTreeNode *pRoot) { if (pRoot == NULL) { return NULL; } BinaryTreeNode *pLastInList = NULL;//指向排好序的双向链表的最后一个结点 Convert(pRoot, pLastInList); while (pLastInList->m_pLeft != NULL)//返回到头结点 { pLastInList = pLastInList->m_pLeft; } return pLastInList; } //以先序的方式构建二叉树,输入-1表示结点为空 void CreateBinaryTree(BinaryTreeNode *&pRoot) { int nNodeValue = 0; cin >> nNodeValue; if (-1 == nNodeValue) { pRoot = NULL; return; } else { pRoot = new BinaryTreeNode(); pRoot->m_nValue = nNodeValue; CreateBinaryTree(pRoot->m_pLeft); CreateBinaryTree(pRoot->m_pRight); } } void PrintInOrder(BinaryTreeNode *&pRoot)//中序遍历二叉树 { if (pRoot != NULL) { PrintInOrder(pRoot->m_pLeft); cout << pRoot->m_nValue << " "; PrintInOrder(pRoot->m_pRight); } } void PrintDoubleListFromLeftToRight(BinaryTreeNode *pRoot)//从左到右打印双向链表 { if (pRoot == NULL) { return; } BinaryTreeNode *pNode = pRoot; while (pNode != NULL) { cout << pNode->m_nValue << " "; pNode = pNode->m_pRight; } cout << endl; } void PrintDoubleListFromRightToLeft(BinaryTreeNode *pRoot)//从右向左打印双向链表 { if (pRoot == NULL) { return; } BinaryTreeNode *pNode = pRoot; while (pNode->m_pRight != NULL) { pNode = pNode->m_pRight; } while (pNode != NULL) { cout << pNode->m_nValue << " "; pNode = pNode->m_pLeft; } cout << endl; } int _tmain(int argc, _TCHAR* argv[]) { BinaryTreeNode *pRoot = NULL; CreateBinaryTree(pRoot); PrintInOrder(pRoot);//4 6 8 10 12 14 16 cout << endl; BinaryTreeNode *pDoubleListHead = ConvertBSTToDoubleList(pRoot); PrintDoubleListFromLeftToRight(pDoubleListHead);//4 6 8 10 12 14 16 PrintDoubleListFromRightToLeft(pDoubleListHead);//16 14 12 10 8 6 4 system("pause"); return 0; }
运行结果: