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

题目：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
　　比如将二元查找树
                                            10
                                          /    \
                                        6       14
                                      /  \     /　 \
                                   　4     8  12 　  16

转换成双向链表
4=6=8=10=12=14=16。
　　分析：本题是微软的面试题。很多与树相关的题目都是用递归的思路来解决，本题也不例外。

我们可以中序遍历整棵树。按照这个方式遍历树，比较小的结点先访问。如果我们每访问一个结点，假设之前访问过的结点已经调整成一个排序双向链表，我们再把调整当前结点的指针将其链接到链表的末尾。当所有结点都访问过之后，整棵树也就转换成一个排序双向链表了。

 

 

#include <stdio.h>
#include <stdlib.h>

#define N 20

int 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<N;i++)
    {
      num = rand()%100 + 50;
      add_tree(&T, num);
    }
  
  printf("tree walk is:\n");
  mid_walk_tree(T);
  
  TREE* head = tree_2_lis t(T);
  
  printf("list walk is:\n");
  print_list(head);
  
  system("PAUSE");    
  return 0;
}