二叉搜索树与双向链表——27-创新互联

  输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表，要求不能创建任何新的结点，只能调整树中结点指针的指向。

如上所示的二叉搜索树，转换成排序的双向链表就是5-><-6-><-7-><-8-><-9-><-10-><-11。

  因为要求转换成双向链表，而恰好二叉树的每个结点都有两个指针，因此可以直接调整指针的指向；对于搜索二叉树，每个结点的左子树的值都比根结点的值要小，而每个右子树的值都比当前结点的值要大，而要求转换成排序的双向链表，因此，对于每个结点的访问顺序应当是先左再中后右，也就是用中序遍历的思路，这样才能保证是有序的；

  对于指针的指向，可以将每个结点指向左结点的指针看做双向链表中指向前一个结点的prev指针，而每个结点指向右结点的指针看做双向链表中指向下一个结点的next指针；因此，对于搜索二叉树的最左结点，其实也就是树中的最小值，也就是双向链表的头结点，而树的最右结点就是链表的尾结点也就是大值；

  观察可发现，对于根结点来说，其prev应该指向的是左子树的最右结点，而next应该指向的是右子树的最左结点，因此对于整棵树来说，可以划分成左右子树来进行递归；

程序设计如下：

#include 
#include 
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<_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:"<_val<_Rnode != NULL)//每个结点的右指针指向下一个结点
    {
        cout<_val<<"->";
        tmp = tmp->_Rnode;
    }
    cout<_val<<"->NULL"<_val<_Lnode != NULL)//每个结点的左指针指向前一个结点
    {
        cout<_val<<"->";
        tmp = tmp->_Lnode;
    }
    cout<_val<<"->NULL"<_Lnode != NULL)//获取链表的头结点
        ListNode = ListNode->_Lnode;

    PrintList(ListNode);

    DestoryBinaryTree(ListNode);
    return 0;
}

运行程序：

《完》

创新互联www.cdcxhl.cn，专业提供香港、美国云服务器，动态BGP最优骨干路由自动选择，持续稳定高效的网络助力业务部署。公司持有工信部办法的idc、isp许可证， 机房独有T级流量清洗系统配攻击溯源，准确进行流量调度，确保服务器高可用性。佳节活动现已开启，新人活动云服务器买多久送多久。