题目要求：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。
参考题目：剑指offer第27题
解决思路：
1. 根据观察可知，双向链表顺序即为二叉树的中序遍历结果----->采用中序遍历+递归；
2. 中序遍历顺序为：左+中+右，传入一个变量pre。
pre可以这样理解：当前结点的pre就是当前结点的前驱。如结点6的前驱是4，结点10的前驱是8.结点4的前驱是NULL。
#includeusing namespace std;typedef struct BinaryTree{ struct BinaryTree *left,*right; int data;}BinaryTree;void initTree(BinaryTree **p);void printList(BinaryTree *list);BinaryTree *treeToList(BinaryTree *pTree);int main(void){ BinaryTree *pTree = NULL,*pList = NULL; initTree(&pTree); pList = treeToList(pTree); printList(pList); return 0;}// 1// / \// 2 3// / \// 4 5void initTree(BinaryTree **p){ *p = new BinaryTree; (*p)->data = 1; BinaryTree *tmpNode = new BinaryTree; tmpNode->data = 2; (*p)->left = tmpNode; tmpNode = new BinaryTree; tmpNode->data = 3; (*p)->right = tmpNode; tmpNode->left = NULL; tmpNode->right = NULL; BinaryTree *currentNode = (*p)->left; tmpNode = new BinaryTree; tmpNode->data = 4; currentNode->left = tmpNode; tmpNode->left = NULL; tmpNode->right = NULL; tmpNode = new BinaryTree; tmpNode->data = 5; currentNode->right = tmpNode; tmpNode->left = NULL; tmpNode->right = NULL;}void printList(BinaryTree *list){ while(list!=NULL) { cout << list->data; if(list->right!=NULL) { cout << "<==>"; } list = list->right; }} //---------------核心代码-----------------------void convert(BinaryTree *pTree,BinaryTree **pre){ if(pTree == NULL) return; BinaryTree *pCurrent = pTree; if(pCurrent->left != NULL) convert(pTree->left,pre); //当前点的前驱为pre pCurrent->left = *pre; //pre不为NULL，pre的后继为当前点 if(*pre != NULL) (*pre)->right = pCurrent; //pre为当前点 *pre = pCurrent; if(pCurrent->right != NULL) convert(pTree->right,pre);}BinaryTree *treeToList(BinaryTree *pTree){ BinaryTree *pre = NULL; convert(pTree,&pre); //按照初始化的树，链表为4<==>2<==>5<==>1<==>3 //此时pre在结点3处，应该返回到结点4处，再遍历输出 while(pre!=NULL && pre->left!=NULL) pre = pre->left; return pre;}