微软面试题1、把二元查找树转变成排序的双向链表

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

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
};

基本思路1：(这个有新节点，用递归，见思路2)

中序遍历二叉树，指针pTree执行当前节点，pFomer指向前一节点，初始为NULL

对出栈节点的操作，p指向从栈顶弹出的节点

pTree->m_pLeft=pFormer;

pFormer->m_pRight=p;

pFomer=pTree;

算法：

 1 View Code 
 2  BSTreeNode * BinTreeToLinkList(BSTreeNode* BT){
 3      Stack S;
 4      BSTreeNode* pTree=BT;
 5      BSTreeNode*list=NULL,*pFormer=NULL;
 6      while(pTree!=NULL||!isEmptyStack(S)){
 7          if(pTree!=NULL){
 8              Push(S,pTree);
 9              pTree=pTree->m_pLeft;
10          }else{
11              pTree=Top(S);
12              if(list==NULL){
13                  list=pTree;
14                  pFormer=pTree;
15              }else{
16                  pFormer->m_pRight=pTree;
17                  pTree->m_pLeft=pFormer;
18                  pFormer=pTree;
19              }
20              pTree=pTree->m_pRight;
21              Pop(S);
22          }
23      }
24      return list;
25  }

为了能够达到要求，只能用中序遍历递归算法了（我一般不用递归的）

基本思路2：和1一样，递归出来的结点顺序就是链表的顺序，往里面加就是了，同样需要list，pFormer

算法：

 BintTree linkList=NULL;//全局变量
 BintTree pFormer=NULL;
 void BinTreeToLinkList(BitTree BT){
       if(BT!=NULL){
            BinTreeToLinkList(BT->lchild);
            if(linkList=NULL){
                linkList=BT;
                pFormer=BT;
           }else{
               pFomer->rchild=BT;
               BT->lchild=pFormer;
               pFormer=BT;
           }
           BinTreeToLinkList(BT->rchild);
       } 
}