输入一棵二叉搜索树，现在要将该二叉搜索树转换成一个排序的双向链表。

//递归
#include<iostream>
#include<stack>
using namespace std;
struct BinaryTreeNode
{
	int data;
	BinaryTreeNode* left;
	BinaryTreeNode* right;
	BinaryTreeNode(int x)
		:data(x)
		, left(NULL)
		, right(NULL)
	{}
};
class BinaryTree
{
protected:
	BinaryTreeNode* _root;
	BinaryTreeNode* _CreateBinaryTree(int* arr, int& index, int size)
	{
		BinaryTreeNode* root = NULL;
		if (index < size&&arr[index] != '#')
		{
			root = new BinaryTreeNode(arr[index]);
			root->left = _CreateBinaryTree(arr, ++index, size);
			root->right = _CreateBinaryTree(arr, ++index, size);
		}
		return root;
	}
	void _Clear(BinaryTreeNode* root)
	{
		if (root == NULL)
			return;
		_Clear(root->left);
		_Clear(root->right);
		delete root;
	}
	void _Convert(BinaryTreeNode* root, BinaryTreeNode** head)//有可能改变head,加引用
	{
		if (root == NULL)
			return;

		BinaryTreeNode* cur = root;

		if (cur->left)
			_Convert(root->left, head);

		cur->left = *head;
		if (*head)
			(*head)->right = cur;

		*head = cur;
		if (cur->right)
			_Convert(cur->right, head);

	}
	//打印并销毁双向链表
private:
	static void PrintList(BinaryTreeNode* head)
	{
		if (head == NULL)
			return;
		BinaryTreeNode* cur = head;
		while (cur)
		{
			cout << cur->data << " ";
			if (cur->left)
				cout << "prev" << cur->left->data << " ";
			if (cur->right)
				cout << "next" << cur->right->data << endl;
			cur = cur->right;
		}
	}
	static void Destroy(BinaryTreeNode** head)
	{
		BinaryTreeNode* cur = *head;
		BinaryTreeNode* del = NULL;
		while (cur)
		{
			del = cur;
			cur = cur->right;
			delete del;
		}
		head = NULL;
	}
public:
	BinaryTree()
		:_root(NULL)
	{}
	~BinaryTree()
	{
		_Clear(_root);
	}
	BinaryTree(int *arr, int size)
	{
		int index = 0;
		_root = _CreateBinaryTree(arr, index, size);
	}
	void PreOrder_Non()
	{
		if (_root == NULL)
			return;
		BinaryTreeNode* cur = _root;
		stack<BinaryTreeNode*> s;
		s.push(_root);
		while (!s.empty())
		{
			cur = s.top();
			printf("%d ", cur->data);
			s.pop();
			if (cur->right)
				s.push(cur->right);
			if (cur->left)
				s.push(cur->left);
		}
	}
	BinaryTreeNode* TransformList()
	{
		if (_root == NULL)
			return NULL;//返回匿名对象
		//应按后序遍历顺序
		BinaryTreeNode* ret = NULL;
		_Convert(_root, &ret);

		while (ret != NULL&&ret->left != NULL)
			ret = ret->left;
		_root = NULL;
		PrintList(ret);
		Destroy(&ret);
	}
};
void Test1()
{
	int arr[] = { 10, 6, 4, '#', '#', 8, '#', '#', 14, 12, '#', '#', 16 };
	BinaryTree bt1(arr, sizeof(arr) / sizeof(arr[0]));
	bt1.PreOrder_Non();
	BinaryTreeNode* head = bt1.TransformList();
}
//非递归
 TreeNode * transfer(TreeNode * root)
{
    // left will be used as previous pointer (point to a little one);
    // right will be used as post pointer (point to a large one);
    if (!root) return NULL;
    Stack *s = new Stack();
    TreeNode *curr, *head, *tail;
    curr = root;
    head = NULL, tail=NULL;
    while(true) {
        while(curr) 
        {
            s->push(curr);
            curr = curr->left;
        }
        
        if(s->isEmpty()) break;
        curr = s->pop();
        //visit(curr);
        //将curr节点加入到双向链表末尾
        if ( head==NULL) 
        { //curr是链表中的第一个节点。
            head = curr;
            tail = curr;
        } 
        else
        {
            tail->right = curr;
            curr->left = tail;
            tail = curr;  //注意此处不能够修改tail->right指针的值，到目前为止，
                          //当前节点的右子树还未被访问。
         
        }
        
        while(!curr->right) 
        {
            if(s->isEmpty()) break;
            curr = s->pop();
            //visit(curr);
            //
            if ( head==NULL) 
            {
                head = curr;
                tail = curr;
            }
            else 
            {
                tail->right = curr;
                curr->left = tail;
                tail = curr; 
            }
        }
        if (curr->right) 
            curr = curr->right;
        else break;
    }

    head->left = NULL;
    tail->right = NULL;
    delete s;
    return head;
}