二叉排序樹轉換成排序的雙向鏈表

題目描述：將二叉排序樹轉換成一個排序的雙向鏈表，要求：不能創建任何新的節點，只能通過調整指針的指向來實現；

解題思路：我們知道二叉排序樹的遞歸定義是：

1. 若它的左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
2. 若它的右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
3. 它的左、右子樹也分別為二叉排序樹；

二叉排序樹的一個很重要的特性就是：二叉樹中序遍歷的結果是一個遞增的序列。由這個特性可以知道該題需要通過中序遍歷的思想來解決。

如上圖所示，我們通過中序遞歸遍歷過程中的一個狀態來解析轉換的過程，當中序遍歷root指向10時，要滿足轉換成雙向有序鏈表的請求，結點10左指針必須指向它中序遍歷的前一個結點8，而前一個結點8的右指針必須指向結點10，代碼如下：

root->left = last;
last->right = root;
last = root;

這樣才能把這兩個結點雙向連接起來，所以總體的思路就是這樣，下面是具體的代碼：

//結點的結構
template<typename Type>
struct BiNode{
Type data;
BiNode *left;
BiNode *right;
};

//二叉排序樹轉換成雙向鏈表
template <typename Type>
void Convert(BiNode<Type> *root, BiNode<Type> *& last)
{
if(root == NULL)
return;

Convert(root->left, last);

root->left = last;
if(last != NULL)
last->right = root;

last = root;

Convert(root->right, last);
}

template <typename Type>
BiNode<Type> * Convert2BinLink( BiNode<Type> *root )
{
if(root == NULL)
return NULL;

BiNode<Type> * last = NULL;

//二叉排序樹轉換成排序雙向鏈表
Convert(root, last);

//取得雙向鏈表的頭指針
while(root->left != NULL)
root = root->left;

return root;
}

推薦閱讀：二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm