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

    輸入一棵二叉搜索樹，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表，要求不能創(chuàng)建任何新的結(jié)點，只能調(diào)整樹中結(jié)點指針的指向。

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

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

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

    觀察可發(fā)現(xiàn)，對于根結(jié)點來說，其prev應(yīng)該指向的是左子樹的最右結(jié)點，而next應(yīng)該指向的是右子樹的最左結(jié)點，因此對于整棵樹來說，可以劃分成左右子樹來進(jìn)行遞歸；

程序設(shè)計如下：

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

struct BinaryTreeNode//二叉樹結(jié)點結(jié)構(gòu)體
{
    int _val;
    BinaryTreeNode *_Lnode;
    BinaryTreeNode *_Rnode;

    BinaryTreeNode(int val)//構(gòu)造函數(shù)
        :_val(val)
         ,_Lnode(NULL)
         ,_Rnode(NULL)
    {}  
};

//創(chuàng)建二叉搜索樹，這里簡便直接使用前序遍歷的方式結(jié)構(gòu)造出了二叉搜索樹
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);
}

//銷毀轉(zhuǎn)變之后的雙向鏈表
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);
    }
}

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

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

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

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

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

    cout<<"ListTail:"<<tmp->_val<<endl;
    cout<<"逆向打印鏈表：";
    while(tmp->_Lnode != NULL)//每個結(jié)點的左指針指向前一個結(jié)點
    {
        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)//獲取鏈表的頭結(jié)點
        ListNode = ListNode->_Lnode;

    PrintList(ListNode);

    DestoryBinaryTree(ListNode);
    return 0;
}

運行程序：

《完》