二叉搜索樹與雙向鏈表——27

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

如上所示的二叉搜索樹，轉換成排序的雙向鏈表就是5-><-6-><-7-><-8-><-9-><-10-><-11。

    因為要求轉換成雙向鏈表，而恰好二叉樹的每個結點都有兩個指針，因此可以直接調整指針的指向；對于搜索二叉樹，每個結點的左子樹的值都比根結點的值要小，而每個右子樹的值都比當前結點的值要大，而要求轉換成排序的雙向鏈表，因此，對于每個結點的訪問順序應當是先左再中后右，也就是用中序遍歷的思路，這樣才能保證是有序的；

    對于指針的指向，可以將每個結點指向左結點的指針看做雙向鏈表中指向前一個結點的prev指針，而每個結點指向右結點的指針看做雙向鏈表中指向下一個結點的next指針；因此，對于搜索二叉樹的最左結點，其實也就是樹中的最小值，也就是雙向鏈表的頭結點，而樹的最右結點就是鏈表的尾結點也就是最大值；

    觀察可發現，對于根結點來說，其prev應該指向的是左子樹的最右結點，而next應該指向的是右子樹的最左結點，因此對于整棵樹來說，可以劃分成左右子樹來進行遞歸；

程序設計如下：

#include <iostream>
#include <assert.h>
using namespace std;

struct BinaryTreeNode//二叉樹結點結構體
{
    int _val;
    BinaryTreeNode *_Lnode;
    BinaryTreeNode *_Rnode;

    BinaryTreeNode(int val)//構造函數
        :_val(val)
         ,_Lnode(NULL)
         ,_Rnode(NULL)
    {}  
};

//創建二叉搜索樹，這里簡便直接使用前序遍歷的方式結構造出了二叉搜索樹
BinaryTreeNode* _Create(const int *arr, size_t& index, size_t size)
{
    if((index < size) && (arr[index] != '#'))
    {   
        BinaryTreeNode* root = new BinaryTreeNode(arr[index]);
        root->_Lnode = _Create(arr, ++index, size);
        root->_Rnode = _Create(arr, ++index, size);
        return root;
    }   
    else
        return NULL;
}

BinaryTreeNode* CreateBinaryTree(const int *arr, size_t size)
{
    assert(arr && size);

    size_t index = 0;
    return _Create(arr, index, size);
}

//銷毀轉變之后的雙向鏈表
void DestoryBinaryTree(BinaryTreeNode* ListNode)
{
    BinaryTreeNode* tmp = ListNode;
    while(ListNode != NULL)
    {
        tmp = ListNode;
        ListNode = ListNode->_Lnode;
        delete tmp;
    }
}

//前序遍歷檢驗二叉樹
void PrevOrder(BinaryTreeNode *root)
{
    if(root != NULL)
    {
        cout<<root->_val<<" ";
        PrevOrder(root->_Lnode);
        PrevOrder(root->_Rnode);
    }
}

//二叉搜索樹轉換為雙向鏈表
void BSTToList(BinaryTreeNode* root, BinaryTreeNode** lastnode)
{
    if(root != NULL)
    {
        BSTToList(root->_Lnode, lastnode);
        root->_Lnode = *lastnode;//如果左結點為空，則當前結點的前指針指向當前鏈表的最后一個結點

        if(*lastnode != NULL)
            (*lastnode)->_Rnode = root;//將當前鏈表的最后一個結點的next指針設置為當前結點

        *lastnode = root;//將鏈表的最后一個結點更新為當前結點
        BSTToList(root->_Rnode, lastnode);//繼續遍歷右子樹直至為空
    }
}

void PrintList(BinaryTreeNode* ListNode)
{
    assert(ListNode);

    BinaryTreeNode* tmp = ListNode;
    cout<<"ListHead:"<<tmp->_val<<endl;
    cout<<"正向打印鏈表：";
    while(tmp->_Rnode != NULL)//每個結點的右指針指向下一個結點
    {
        cout<<tmp->_val<<"->";
        tmp = tmp->_Rnode;
    }
    cout<<tmp->_val<<"->NULL"<<endl;

    cout<<"ListTail:"<<tmp->_val<<endl;
    cout<<"逆向打印鏈表：";
    while(tmp->_Lnode != NULL)//每個結點的左指針指向前一個結點
    {
        cout<<tmp->_val<<"->";
        tmp = tmp->_Lnode;
    }
    cout<<tmp->_val<<"->NULL"<<endl;
}

int main()
{
    int arr[] = {8,6,5,'#','#',7,'#','#',10,9,'#','#',11,'#','#'};

    BinaryTreeNode* root = CreateBinaryTree(arr, sizeof(arr)/sizeof(arr[0]));
    cout<<"PrevOrder: ";
    PrevOrder(root);
    cout<<endl;

    BinaryTreeNode* lastnode = NULL;
    BSTToList(root, &lastnode);

    BinaryTreeNode* ListNode = root;
    while(ListNode->_Lnode != NULL)//獲取鏈表的頭結點
        ListNode = ListNode->_Lnode;

    PrintList(ListNode);

    DestoryBinaryTree(ListNode);
    return 0;
}

運行程序：

《完》