【微软面试一百题：1】把二元查找树转变成排序的双向链表

题目：

输入一棵二元查找树,将该二元查找树转换成一个排序的双向链表。 要求不能创建任何新的结点,只调整指针的指向。
10
/
6 14
/ \ / \
4 8 12 16
转换成双向链表 ：4=6=8=10=12=14=16
hint: 二叉树的中序遍历

#include<iostream>
#include <string>
using namespace std;

struct BSTreeNode
{
    int value;
    BSTreeNode *left;
    BSTreeNode *right;
};

typedef BSTreeNode DoubleList;
DoubleList * headPtr;
DoubleList * indexPtr;
void AddBSTreeNode(BSTreeNode * &pCurrent,int value);
void vist(BSTreeNode * root);
void convertToList(BSTreeNode * p);
int main()
{
    BSTreeNode * root = NULL;
  
    AddBSTreeNode(root, 10);
    AddBSTreeNode(root, 4);
    AddBSTreeNode(root, 6);
    AddBSTreeNode(root, 8);
    AddBSTreeNode(root, 12);
    AddBSTreeNode(root, 14);
    AddBSTreeNode(root, 16);
    vist(root);
    return 0;
}

void AddBSTreeNode(BSTreeNode * &pCurrent,int value)
{
    if (NULL == pCurrent) {
        BSTreeNode * newNode = new BSTreeNode;
        newNode->left=NULL;
        newNode->right=NULL;
        newNode->value = value;
        pCurrent = newNode;
    }else{
        if (pCurrent->value>value) {
            AddBSTreeNode(pCurrent->left, value);
        }else if (pCurrent->value<value)
            AddBSTreeNode(pCurrent->right, value);
        
    }
}

void vist(BSTreeNode * root)
{
    if (NULL==root)
        return;
    vist(root->left);
    //cout<<root->value<<endl;
    convertToList(root);
    vist(root->right);
}
void convertToList(BSTreeNode *p)
{
    if (NULL==headPtr) {
        headPtr = p;
        indexPtr = p;
        
    }else{
        
    indexPtr->right = p;
    p->left = indexPtr;
    indexPtr = p;
        
    }
    cout<<p->value<<endl;

}