輸入一棵二叉搜索樹，現在要將該二叉搜索樹轉換成一個排序的雙向鏈表。

一、問題描述

輸入一棵二叉搜索樹，現在要將該二叉搜索樹轉換成一個排序的雙向鏈表。而且在轉換的過程中，不能創建任何新的結點，只能調整樹中的結點指針的指向來實現。

二、實現思路

在二叉搜索樹中，每個結點都有兩個分別指向其左、右子樹的指針，左子樹結點的值總是小于父結點的值，右子樹結點的值總是大于父結點的值。而在雙向鏈表中，每個結點也有兩個指針，它們分別指向前一個結點和后一個結點。所以這兩種數據結構的結點是一致，二叉搜索樹之所以為二叉搜索樹，雙向鏈表之所以為雙向鏈表，只是因為兩個指針的指向不同而已

思路：在轉換成排序雙向鏈表時，原先指向左子結點的指針調整為鏈表中指向前一個結點的指針，原先指向右子結點的指針調整為鏈表中指向下一個結點的指針。對于樹的操作，通常是在遍歷樹的各個結點的過程中，通過對結點實施某些操作來完成的，這個算法也不例外。由于要求轉換后的雙向鏈表也是有序的，而我們從上面也可以看到，當我們以中序遍歷二叉搜索樹時，其遍歷的結點就是有序的，所以在這里采用的遍歷順序應該是中序。

//遞歸
#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;
}

我們有一個變量head用來記錄轉換了的鏈表末結點，由于在慣例中，我們會返回鏈表的第1個結點（從1開始計數）的指針，而head指向的卻是末結點，我們可以通過該指針來從尾走到頭來獲取第一個結點的指針，但是在這里我卻沒有這樣做，因為它需要對每個結點都遍歷一次，時間復雜度為O（n）。而是在變換前，找到二叉排序樹的最左結點的指針。因為排序二叉樹是有序的，最左的結點即為最小的結點，而我們的算法也不會刪除或新增結點，也就是說結點的地址是不會改變的，所以最左的結點就是轉換后的鏈表的第1個結點，其時間復雜度為O（logN）。

該算法首先從根要點一直向左走，找到最左邊的結點，其時間復雜度為O(logN)，然后對二叉排序樹中的每個結點遍歷一次，進行指針變換，其時間復雜度為O(N)，所以總的時間復雜度為O(N)。

至于空間復雜度，由于ConvertNode函數進行遞歸調用，其函數有兩個開參，而函數棧中的函數調用層數不會超過樹高，所以其空間復雜度為O(logN)。