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

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

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

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

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

程序設(shè)計(jì)如下：

#include 
#include 
using namespace std;

struct BinaryTreeNode//二叉樹結(jié)點(diǎn)結(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;
    }
}

//前序遍歷檢驗(yàn)二叉樹
void PrevOrder(BinaryTreeNode *root)
{
    if(root != NULL)
    {
        cout<_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é)點(diǎn)為空，則當(dāng)前結(jié)點(diǎn)的前指針指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)

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

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

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

    BinaryTreeNode* tmp = ListNode;
    cout<<"ListHead:"<_val<_Rnode != NULL)//每個(gè)結(jié)點(diǎn)的右指針指向下一個(gè)結(jié)點(diǎn)
    {
        cout<_val<<"->";
        tmp = tmp->_Rnode;
    }
    cout<_val<<"->NULL"<_val<_Lnode != NULL)//每個(gè)結(jié)點(diǎn)的左指針指向前一個(gè)結(jié)點(diǎn)
    {
        cout<_val<<"->";
        tmp = tmp->_Lnode;
    }
    cout<_val<<"->NULL"<_Lnode != NULL)//獲取鏈表的頭結(jié)點(diǎn)
        ListNode = ListNode->_Lnode;

    PrintList(ListNode);

    DestoryBinaryTree(ListNode);
    return 0;
}

運(yùn)行程序：

《完》

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務(wù)器買多久送多久。