题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
比如将二元查找树 10 / \ 6 14 / \ / \ 4 8 12 16 转换成双向链表 4=6=8=10=12=14=16。 分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。
#include#include #define N 20int count = 0;typedef struct tree{ int num; struct tree* lchild; struct tree* rchild;}TREE;int add_tree(TREE** T, int num){ if(*T == NULL) { *T = (TREE*)malloc(sizeof(TREE)); (*T)->num = num; (*T)->lchild = NULL; (*T)->rchild = NULL; } else if((*T)->num < num) return add_tree(&((*T)->rchild),num); else return add_tree(&((*T)->lchild),num);}int mid_walk_tree(TREE* T){ if(T!=NULL) { mid_walk_tree(T->lchild); count++; if(count%10 == 0) printf("%d\n",T->num); else printf("%d\t",T->num); mid_walk_tree(T->rchild); }}int convert_node(TREE* T,TREE** L){ if(T == NULL) return 0; TREE* pCurrent = T; if(pCurrent->lchild != NULL) convert_node(pCurrent->lchild, L); pCurrent->lchild = *L; if(*L != NULL) (*L)->rchild = pCurrent; *L = pCurrent; if(pCurrent->rchild != NULL) convert_node(pCurrent->rchild, L);}TREE* tree_2_list(TREE* T){ TREE* L = NULL; convert_node(T, &L); TREE* list_head = L; L->rchild = NULL; while(list_head && list_head->lchild) list_head = list_head->lchild; return list_head;}void print_list(TREE* H){ count = 0; if(H!=NULL) printf("H is not null\n"); else { printf("H is null\n"); return; } while(H!=NULL) { count++; if(count%10 == 0) printf("%d\n",H->num); else printf("%d\t",H->num); H = H->rchild; }}int main(int argc, char *argv[]){ srand((unsigned)time(NULL)); TREE* T = NULL; int num; int i = 0; for(;i