把二元查找树转变成排序的双向链表

题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。
10
/ \
6 14
/ \ / \
4 8 12 16
转换成双向链表
4=6=8=10=12=14=16。
首先我们定义的二元查找树 节点的数据结构如下：

struct BSTreeNode
{
int m_nValue; // value of node
BSTreeNode *m_pLeft; // left child of node
BSTreeNode *m_pRight; // right child of node
};

 

思路： 第一种方法，利用中序遍历思想，由于中序遍历出来的结果正好有序，因此按照中序遍历输出的结果顺序串成有序链表。

#include <stdio.h>
#include <stdlib.h>

typedef struct BSTreeNode
{
    int m_nValue;
    BSTreeNode *m_pleft;
    BSTreeNode *m_pright;
}BSTreeNode;
BSTreeNode *current_node, *first_node;

void insertNode(BSTreeNode **proot, BSTreeNode **pNode)
{
    BSTreeNode *node, *pnode, *pre_node;

    if(*proot == NULL)
    {
        *proot = *pNode;
        return;
    }

    pnode = *pNode;
    node = *proot;
    pre_node = NULL;

    while(node)
    {
        pre_node = node;
        if(node->m_nValue == pnode->m_nValue)
        {
            free(pnode);
            return;
        }
        if(node->m_nValue > pnode->m_nValue)
            node = node->m_pleft;
        else
            node = node->m_pright;
    }
    if(pre_node->m_nValue > pnode->m_nValue)
        pre_node->m_pleft = pnode;
    else
        pre_node->m_pright = pnode;

}

void print(BSTreeNode *node)
{
    if(node)
    {
        print(node->m_pleft);
        if(current_node == NULL)
        {
            current_node = node;
            first_node = node;
        }
        else
        {
            current_node->m_pright = node;
            node->m_pleft = current_node;
        }
        current_node = node;
        print(node->m_pright);
    }
}


int main()
{
    int i, j;
    int n, m;
    BSTreeNode *root, *newNode;

    while(scanf("%d", &n) != EOF)
    {
        root = NULL;
        current_node = NULL;
        first_node = NULL;
        for(i = 0; i < n; i )
        {
            scanf("%d", &m);

            newNode = (BSTreeNode *)malloc(sizeof(BSTreeNode));
            newNode->m_nValue = m;
            newNode->m_pleft = NULL;
            newNode->m_pright = NULL;
            insertNode(&root, &newNode);
        }
        print(root);
        newNode = first_node;
        while(newNode)
        {
            printf("%d ", newNode->m_nValue);
            newNode = newNode->m_pright;
        }
    }
}

    第二种方法： 利用分治思想，先处理左子树，后处理右子树，最后利用根结点将处理完的有序左子树与有序右子树连接起来，实现将二元查找树转换成有序双链表的目的。

#define LEFT -1
#define RIGHT 1

BSTreeNode* change(BSTreeNode *node, int dir)
{
    BSTreeNode *ptmp = NULL;
    BSTreeNode *pleft = NULL;
    BSTreeNode *pright = NULL;
    if(node->m_pleft)
        pleft = change(node->m_pleft, LEFT);
    if(node->m_pright)
        pright = change(node->m_pright, RIGHT);
    if(pleft)
    {
        node->m_pleft = pleft;
        pleft->m_pright = node;
    }
    if(pright)
    {
        node->m_pright = pright;
        pleft->m_pleft = node;
    }
    ptmp = node;
    if(dir == LEFT)
    {
        while(ptmp->m_pright)
            ptmp = ptmp->m_pright;
    }
    if(dir == RIGHT)
    {
        while(ptmp->m_pleft)
            ptmp = ptmp->m_pleft;
    }
    return ptmp;
}