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

#include<iostream>

using namespace std;

  

struct BSTreeNode {

    int m_nValue;

    BSTreeNode * m_pLeft;

    BSTreeNode * m_pRight;

    BSTreeNode(int value){

        m_nValue = value;

        m_pLeft = NULL;

        m_pRight = NULL;

    }

};

  

BSTreeNode * BSTreeNodeList[7];

  

BSTreeNode * buildTestTree() {

    int values [7] = {10,6,14,4,8,12,16};

    for(int i=0;i<sizeof(values)/sizeof(int);i++){

        BSTreeNodeList[i] = new BSTreeNode(values[i]);

    }

    BSTreeNode * root = BSTreeNodeList[0];

    root->m_pLeft = BSTreeNodeList[1];

    root->m_pRight = BSTreeNodeList[2];

  

    BSTreeNodeList[1]->m_pLeft = BSTreeNodeList[3];

    BSTreeNodeList[1]->m_pRight = BSTreeNodeList[4];

  

    BSTreeNodeList[2]->m_pLeft = BSTreeNodeList[5];

    BSTreeNodeList[2]->m_pRight = BSTreeNodeList[6];

  

    return root;

}

  

BSTreeNode * tail = NULL;

BSTreeNode * head = NULL;

  

void scan(BSTreeNode * root) {

    if (root == NULL) return ;

    scan(root->m_pLeft);

    if(tail == NULL) head = root;

    root->m_pLeft = tail;

    if (tail != NULL) tail->m_pRight = root;

    tail = root;

    scan(root->m_pRight);

}

  

int main(){

    BSTreeNode * root = buildTestTree();

    scan(root);

    BSTreeNode * p = head;

    while(p!=NULL){

        cout<<p->m_nValue<<endl;

        p = p->m_pRight;

    }

    cout<<"------------"<<endl;

    p = tail;

    while(p!=NULL){

        cout<<p->m_nValue<<endl;

        p = p->m_pLeft;

    }

    return 0;

}