convert BST into double linked list

二叉搜索树转换为排序的双向链表

如果允许使用额外的空间，中序遍历二叉搜索树即可，每遍历到一个节点，就把其插入到双向链表中。

这里要讲的是无需额外空间的方法。

                                           20
                                          /    \
                                        10     30
                                      /  \     /　 \
                                    8    15 24 　32
转换成双向链表

8--10--15--20--24--30--32。

先定义一个二叉搜索树的结构和其上的插入操作，在其中加入上述节点，
然后定义函数BST2DLL()，将二叉搜索树转换为排序的双向链表。

struct node {     //二叉搜索树节点定义
    int data;
    struct node* left;
    struct node* right;
};

void tree_insert(struct node * root, struct node * new_node){  //插入节点的方法
    
    struct node * curr1 = root;
    struct node * curr2 = curr1;
    while(curr1 != NULL){    //curr1沿路径下降，而curr2始终指向curr1的父节点。
        curr2 = curr1;
        if(new_node->data <= curr->data)
            curr1 = curr1->left;
        else
            curr1 = curr1->right;
    }
    if(curr2 == NULL){  //这说明root本来就是NULL
        root = new_node;
    }else{
        if(new_node->data < curr2->data)
            curr2->left = new_node;
        else
            curr2->right = new_node;
    }
}

int main(){
    struct node * BSTree;
    int array[7] = {15,20,10,8,30,24,32};
    for(int i=0; i<7; i++){
        struct node *new_node = (struct node *)malloc(sizeof(struct node));
        new_node->data = array[i];
        new_node->left = new_node->right = NULL;
        tree_insert(BSTree, new_node);

    struct node * DLL = BST2DLL(BSTree,1);
    //BST2DLL执行后，效果还不完全是双向链表， 8=10=15=20=24=30=32,但是8和32之间还没连接。
    //可通过一次遍历构造8和32直接的连接。
    struct node * tmp = DLL;
    while(tmp->right != NULL)
        tmp++;
    DLL->left = tmp;
    tmp->right = DLL;
    //此时DLL指向的才是一个真正的双向链表
    
    
}
//引入is_right_flag的作用：is_right_flag为1，返回的是指向链表最左端的元素的指针；
//                                            is_right_flag为0，返回的是指向链表最右端的元素的指针；
//这是为了红色部分执行合并时的正确性

struct node * BST2DLL(struct node * root，int is_right_flag){
    if(root == NULL)
        return root;

    if(root->left != NULL)
        left_tree = BST2DLL(root->left, 0);
    if(left_tree != NULL){
        left_tree->right = root;
        root->left = left_tree;
    }

    if(root->right != NULL)
        right_tree = BST2DLL(root->right, 1);
    if(right_tree != NULL){
        right_tree->left = root;
        root->right = right_tree;
    }

    struct node * ptmp = root;
    if(is_right_flag)
        while(ptmp->left != NULL)
            ptmp = ptmp->left;
    else
         while(ptmp->right != NULL)
             ptmp = ptmp->right;

    return ptmp;
}