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

题目：
输入一棵二叉排序树，将该二叉排序树转换成一个排序的带头结点的双向链表。
如：

转换成双向链表
4<->6<->8<->10<->12<->14<->16

关键代码：

code1.PNG code2.PNG

运行截图：

run.PNG

全部代码：

/*
    2016110131
    邵博超
    数据结构第三次作业
*/ 
#include<stdio.h>
#include<malloc.h>
#include<iostream>

using namespace std;
typedef int TElemType;
typedef struct BiTNode { // 结点结构
    TElemType      data;
    struct BiTNode  *lchild, *rchild;
    // 左右孩子指针
} BiTNode, *BiTree;


//InsertNode
//二叉排序树插入
void InsertNode(BiTree &T,TElemType x) {
    if(T==NULL) {
        //cout<<"null"<<endl;
        T = (BiTree)malloc(sizeof(BiTNode));
        T->data = x;
        cout<<"Insert:"<<x<<endl;
        T->rchild = T->lchild = NULL;

    } else {
        //cout<<"not null"<<endl;
        if(x<=T->data)
            InsertNode(T->lchild,x);

        else
            InsertNode(T->rchild,x);
    }

}

//PreOrderPrint
void PreOrderPrint(BiTree& T) {
    if(T) {
        cout<<T->data<<" ";
        PreOrderPrint(T->lchild);
        PreOrderPrint(T->rchild);
    }
}

void PreOrderPrintNode(BiTNode *N) {
    if(N) {
        cout<<N->data<<" ";
        PreOrderPrint(N->lchild);
        PreOrderPrint(N->rchild);
    }
}

//二叉排序树转换成双向链表
void Convert(BiTNode *root,BiTNode *& last) {
    if(root==NULL)
        return;
    Convert(root->lchild,last);
    root->lchild = last;
    if(last!=NULL)
        last->rchild = root;

    last = root;
    Convert(root->rchild,last);
}

BiTNode* Convert2BiLink(BiTNode *root) {
    if(root==NULL)
        return NULL;

    BiTNode* last = NULL;

    //转换为排序双向链表
    Convert(root,last);

    //取得双向链表头指针
    while(root->lchild=NULL)
        root = root->lchild;

    return root;
}

BiTNode* ConvertTree(BiTNode* root) {
    if (root == NULL || (root->lchild == NULL && root->rchild == NULL))
        return root;
    //转换左子树 
    BiTNode* left = ConvertTree(root->lchild);
    if(left) {
        while(left->rchild) left = left->rchild;
        //连接左子树最右端节点 
        left->rchild = root;
        root->lchild = left;
    }
    //转换右子树 
    BiTNode*right = ConvertTree(root->rchild);
    if (right) {
        while(right->lchild) right = right->lchild;
        //连接右子树最左端节点 
        root->rchild = right;
        right->lchild = root;
    }
    return root;
}

BiTNode* Convert(BiTNode* root) {
    root = ConvertTree(root);
    while(root && root->lchild) root = root->lchild;
    return root;
}


int main() {
    BiTree T=NULL;
    cout<<"--插入值（二叉排序树）--"<<endl;
    int values[10] = {4,6,8,10,12,14,16,100,200,-10};
    for(int i=0; i<10; i++)
        InsertNode(T,values[i]);
    /*
    for(int i=0; i<10; i++)
        InsertNode(T,i);
    for(int i=-10; i<0; i++)
        InsertNode(T,i);
    */
    cout<<endl;
    cout<<"PreOrderPrint:";
    PreOrderPrint(T);
    cout<<endl<<endl<<"--二叉排序树转换为排序双向链表--"<<endl;
    BiTNode* head = Convert(T);
    while(head) {
        cout << head->data << " ";
        head = head->rchild;
    }
}