题目：

输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。

要求不能创建任何新的结点，只调整指针的指向。

根据提供的思路，我自己写了一个读入任意序列的整数，建立二叉查找树再改成链表的C++代码:

#include 
     
      #include 
      
       #include 
       
        using namespace std;// binary search tree nodestruct BSTreeNode{    int value;    struct BSTreeNode *leftChild;    struct BSTreeNode *rightChild;};void addBSTreeNode(struct BSTreeNode **ppRoot/*double pointer to the root*/, int new_value);void printBSTree(ofstream *fout, struct BSTreeNode *root, int level);void treeToLinkedList(struct BSTreeNode **ppHead, struct BSTreeNode **ppTail, struct BSTreeNode *root);int main() {    ifstream fin ("tree_to_linked_list.in");    ofstream fout ("tree_to_linked_list.out");    int in;    struct BSTreeNode *root = NULL, *head = NULL, *tail = NULL, *node = NULL;    if(fin.good() == false)    {        cerr << "file open failed" << endl;        return 0;    }    while(true)    {        if(fin.eof())            break;        fin >> in;        addBSTreeNode(&root, in);    }    printBSTree(&fout, root, 0);    fout << endl;    treeToLinkedList(&head, &tail, root);    for(node = head; node != NULL; node = node->rightChild)    {        fout << node->value << " ";    }    fout << endl;    for(node = tail; node != NULL; node = node->leftChild)    {        fout << node->value << " ";    }    fout << endl;    return 0;}void addBSTreeNode(struct BSTreeNode **ppRoot/*double pointer to the root*/, int new_value){    if(*ppRoot == NULL)    {        *ppRoot = new struct BSTreeNode();        (*ppRoot)->value = new_value;                return;    }    if(new_value == (*ppRoot)->value)    {        return;    }    else if(new_value < (*ppRoot)->value)    {        addBSTreeNode(&(*ppRoot)->leftChild, new_value);    }    else    {        addBSTreeNode(&(*ppRoot)->rightChild, new_value);    }}void printBSTree(ofstream *pFout, struct BSTreeNode *root, int level){    if(root == NULL)        return;    printBSTree(pFout, root->leftChild, level + 1);    int i;    for(i = 0; i < level; i ++)        (*pFout) << "\t";    (*pFout) << root->value << endl;    printBSTree(pFout, root->rightChild, level + 1);}void treeToLinkedList(struct BSTreeNode **ppHead, struct BSTreeNode **ppTail, struct BSTreeNode *root){    struct BSTreeNode *ltemp, *rtemp;    if(root == NULL)    {        (*ppHead) = NULL;        (*ppTail) = NULL;        return;    }    treeToLinkedList(ppHead, &ltemp, root->leftChild);    treeToLinkedList(&rtemp, ppTail, root->rightChild);    if(*ppHead == NULL)    {        (*ppHead) = root;        root->leftChild = NULL;    }    else    {        root->leftChild = ltemp;        ltemp->rightChild = root;    }    if(*ppTail == NULL)    {        (*ppTail) = root;        root->rightChild = NULL;    }    else    {        root->rightChild = rtemp;        rtemp->leftChild = root;    }}
       
      
     

 

样例输入:

10 5 14 45 64 3 7 12 11 33 52 63 23 46 73 44 66 22 45 67 78 83

 

样例输出：

3    5        710            11        12    14                    22                23            33                44        45                    46                52                    63            64                    66                        67                73                    78                        833 5 7 10 11 12 14 22 23 33 44 45 46 52 63 64 66 67 73 78 83 83 78 73 67 66 64 63 52 46 45 44 33 23 22 14 12 11 10 7 5 3