微软系列面试题c/c++第一题双向链表

先写的别的，近来学习算法和数据结构，有许多不懂的地方，借助代码提高一下自己的能力。在此，做个计划，每两天写一篇博客，解决一道微软面试题。打算一年之内完成系列博客的更新。也请大家多多探讨。也算是对自己的一个贵在坚持的锻炼。

第一道题是把二元查找树转变成排序的双向链表。

在数据结构中，二元查找树是树的左子树比根节点小，右子树比根节点大。每一颗子树也是二元查找树。二元查找树的中序遍历是升序的。

/*

  Problem_1.cpp
  author:B11040805
*/

#include<stdio.h>
struct BSTreeNode{
int value;
struct BSTreeNode *pLeft,*pRight;
BSTreeNode(){
pLeft=pRight=NULL;
}
};
BSTreeNode *head=NULL,*tail=NULL;

void createList(BSTreeNode *cur){
cur->pLeft=tail;
if(tail!=NULL){
tail->pRight=cur;
}else{
head=cur;
}
tail=cur;
}



BSTreeNode* visit(BSTreeNode *root)
{
if(root!=NULL){
visit(root->pLeft);
createList(root);
visit(root->pRight);
}
return root;
}

void addNode(BSTreeNode **root,int value){
BSTreeNode *p;
if(NULL!=*root)
{
if(value>(*root)->value){
addNode(&((*root)->pRight),value);
}else if(value<(*root)->value){
addNode(&((*root)->pLeft),value);
}else{
printf("error");
}
}else{
p=new BSTreeNode();
p->value=value;
*root=p;
}
}

int main(){
BSTreeNode *root=NULL;
int data[]={10,6,14,4,8,12,16};
for(int i=0;i<7;i++)
{
addNode(&root,data[i]);
}
visit(root);
while(tail!=NULL){
printf("%d  ",tail->value);
tail=tail->pLeft;
}
printf("\n");
while(head!=NULL){
printf("%d  ",head->value);
head=head->pRight;
}
return 0;
}