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

描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。
要求不能创建任何新的结点，只调整指针的指向。

比如将二元查找树

                                        10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                   　4     8  12 　  16
转换成双向链表4=6=8=10=12=14=16。

要做的工作：
1、将输入的无序序列转换成二叉查找树。
2、中序遍历该二元查找树，并在遍历的过程中调整指针，将它调整为双向链表。

由无序序列创建二元查找树的2中方法如下：

//方法1:
//创建二元查找树
void addBSTreeNode(BiNode *&pCurrent,int value)
{
    if(pCurrent==NULL)
    {
        BiNode *pnode=new BiNode;
        pnode->m_pLeft=NULL;
        pnode->m_pRight=NULL;
        pnode->m_value=value;
        pCurrent=pnode;
    }
    else
    {
        if((pCurrent->m_value) > value)
        {
            addBSTreeNode(pCurrent->m_pLeft,value);
        }
     else if((pCurrent->m_value) < value)
        {
            addBSTreeNode(pCurrent->m_pRight,value);
        }
     else
        {
            cout<<"重复节点"<<endl;
        }

    }
}

*/

    

//方法二：
//由无序序列创建二元查找树
bool SearchBST(BiTree T,int key,BiTree f,BiTree &p)
{
    if(!T)
    {
        p=f;
        return false;
    }
    else if(key==(T->m_value))
    {
        p=T;
        return true;
    }
    else if(key<(T->m_value))
        return SearchBST(T->m_pLeft,key,T,p);
    else
        return SearchBST(T->m_pRight,key,T,p);


}


bool InsertBST(BiTree &T,int key)
{
    if(!SearchBST(T,key,NULL,p))
    {
        s=(BiTree)malloc(sizeof(BiNode));
        s->m_value=key;
        s->m_pLeft=s->m_pRight=NULL;
        if(!p)
        {
            T=s;
        }
        else if(key<p->m_value)
        {
            p->m_pLeft=s;
        }
        else
            p->m_pRight=s;
        return true;
    }
    else
        return false;
}

完整源代码如下：

//test01.cpp
#include<iostream>
using namespace std;

typedef struct BiNode
{
    BiNode *m_pLeft;
    BiNode *m_pRight;
    int m_value;
}BiNode,*BiTree;

BiNode *pHead;
BiNode *pListIndex;
BiTree s=NULL;
BiTree p=NULL;

void convertToDoubleList(BiNode *pCurrent);


/*
//创建二元查找树方法1：
void addBSTreeNode(BiNode *&pCurrent,int value)
{
    if(pCurrent==NULL)
    {
        BiNode *pnode=new BiNode;
        pnode->m_pLeft=NULL;
        pnode->m_pRight=NULL;
        pnode->m_value=value;
        pCurrent=pnode;
    }
    else
    {
        if((pCurrent->m_value) > value)
        {
            addBSTreeNode(pCurrent->m_pLeft,value);
        }
     else if((pCurrent->m_value) < value)
        {
            addBSTreeNode(pCurrent->m_pRight,value);
        }
     else
        {
            cout<<"重复节点"<<endl;
        }

    }
}

*/
//创建二元查找树方法二：
bool SearchBST(BiTree T,int key,BiTree f,BiTree &p)
{
    if(!T)
    {
        p=f;
        return false;
    }
    else if(key==(T->m_value))
    {
        p=T;
        return true;
    }
    else if(key<(T->m_value))
        return SearchBST(T->m_pLeft,key,T,p);
    else
        return SearchBST(T->m_pRight,key,T,p);


}


bool InsertBST(BiTree &T,int key)
{
    if(!SearchBST(T,key,NULL,p))
    {
        s=(BiTree)malloc(sizeof(BiNode));
        s->m_value=key;
        s->m_pLeft=s->m_pRight=NULL;
        if(!p)
        {
            T=s;
        }
        else if(key<p->m_value)
        {
            p->m_pLeft=s;
        }
        else
            p->m_pRight=s;
        return true;
    }
    else
        return false;
}





//中序遍历2元查找树
void ergodicBSTree(BiNode *pCurrent)
{
    if(pCurrent==NULL)
        return;
    if(NULL!=pCurrent->m_pLeft)
    {
        ergodicBSTree(pCurrent->m_pLeft);
    }

    convertToDoubleList(pCurrent);

    if(NULL!=pCurrent->m_pRight)
    {
        ergodicBSTree(pCurrent->m_pRight);
    }

}


//转换为双向链表
void convertToDoubleList(BiNode *pCurrent)
{
    pCurrent->m_pLeft=pListIndex;
    if(NULL!=pListIndex)
    {
        pListIndex->m_pRight=pCurrent;
    }
    else
    {
        pHead=pCurrent;
    }
    pListIndex=pCurrent;
    cout<<pCurrent->m_value<<endl;
}


int main()
{

    BiNode *pRoot=NULL;
    pHead=NULL;
    pListIndex=NULL;

    InsertBST(pRoot,4);
    InsertBST(pRoot,6);
    InsertBST(pRoot,7);
    InsertBST(pRoot,7);
    InsertBST(pRoot,9);
    InsertBST(pRoot,14);
    InsertBST(pRoot,8);
    InsertBST(pRoot,16);
    /*
    addBSTreeNode(pRoot,10);
    addBSTreeNode(pRoot,4);
    addBSTreeNode(pRoot,6);
    addBSTreeNode(pRoot,8);
    addBSTreeNode(pRoot,12);
    addBSTreeNode(pRoot,14);
    addBSTreeNode(pRoot,15);
    addBSTreeNode(pRoot,16);
    */
    ergodicBSTree(pRoot);
    return 0;
}

  运行结果如下：