输入：一棵二叉排序树
输出：双向链表
要求：不能创建任何新的结点，只调整指针的指向。
算法设计思想：
- 构造一棵二叉排序树。
- 中序遍历二叉排序树，在访问结点时调整成一个双向链表的结点，即将其左右孩子指针转化成前驱和后继指针。
源码如下
1 #include"stdafx.h" 2 #include3 using namespace std; 4 5 struct BSTNode 6 { 7 int m_Value; 8 BSTNode *leftChild; 9 BSTNode *rightChild;10 11 };12 13 void AddBSTNode(BSTNode *&pNode, int value);14 void InorderBST(BSTNode *BST);15 void ConvertToDLinkList(BSTNode *pNode);16 BSTNode *pHead = nullptr;17 BSTNode *preNode = nullptr;18 19 int main()20 {21 BSTNode *pRoot = nullptr;22 AddBSTNode(pRoot, 10);23 AddBSTNode(pRoot, 6);24 AddBSTNode(pRoot, 14);25 AddBSTNode(pRoot, 4);26 AddBSTNode(pRoot, 8);27 AddBSTNode(pRoot, 12);28 AddBSTNode(pRoot, 16);29 BSTNode *tmpRoot = pRoot;30 InorderBST(tmpRoot);31 }32 33 void AddBSTNode(BSTNode *&pNode, int value)34 {35 if (pNode == nullptr)36 {37 BSTNode *tempNode = new BSTNode();38 tempNode->m_Value = value;39 tempNode->leftChild = nullptr;40 tempNode->rightChild = nullptr;41 pNode = tempNode;42 }43 else if (pNode->m_Value < value)44 {45 AddBSTNode(pNode->rightChild, value);46 }47 else if (pNode->m_Value > value)48 {49 AddBSTNode(pNode->leftChild, value);50 }51 else52 {53 cout << "该结点已经存在，勿重复添加\n";54 }55 }56 57 void InorderBST(BSTNode *BST)58 {59 if (BST == nullptr)60 return;61 InorderBST(BST->leftChild);62 //cout << BST->m_Value;63 ConvertToDLinkList(BST);64 InorderBST(BST->rightChild);65 }66 67 void ConvertToDLinkList(BSTNode *pNode)68 {69 pNode->leftChild = preNode;70 if (nullptr == preNode)71 {72 pHead = pNode;73 }74 else75 {76 preNode->rightChild = pNode;77 }78 preNode = pNode;79 cout << pNode->m_Value << ' ';80 }