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

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

转换成双向链表
4=6=8=10=12=14=16。

 

  题目有一点是必须注意的,转换为排序的双向链表,这就是二叉树的中序遍历了.

 

  二叉树的递归中序遍历为:

    midwalk(T->lchild)

    printf...

    midwalk(T->rchild)

 

 

  有了这概念就好说了,链表有个重要的东西,就是要保存当前节点的值（这个值是变化的）,这个时候就要用指针的指针了...ok,代码如下:

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

#define MAX_NUM 10

typedef struct tree
{
  int num;
  struct tree* lchild;
  struct tree* rchild;
}TREE;
 
int count = 0;

void 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 )
   add_tree(&((*T)->lchild), num);
  else
   add_tree(&((*T)->rchild), num);
}

void mid_walk(TREE* T)
{
  if(T!=NULL)
   {
     mid_walk(T->lchild);
     count++;
     if(count%5==0)
        printf("%d\n",T->num);
     else
        printf("%d\t",T->num);
     
     mid_walk(T->rchild);
   }
}
/*注意这里的P是指针的指针,这里的P就是当前指针的值了,最开始为NULL*/
void convertnode(TREE* T,TREE** P)
{
 if(T==NULL)
   return;
  
  if(T->lchild)
    convertnode( T->lchild, P);
  
  T->lchild = *P;
  if(*P!=NULL)
    (*P)->rchild = T;
   
  *P = T;
  if(T->rchild)
    convertnode( T->rchild, P);    
}


/*寻找最左的节点*/
TREE* find_head(TREE* T)
{
  TREE* p = T;
  while(p&&p->lchild)
     p = p->lchild;
    
  return p;
}

void print_list(TREE* L, int flag)
{
   TREE* p = L;
   while(p!=NULL)
    {
     count++;
     if(count%5==0)
      printf("%d\n",p->num);
     else
      printf("%d\t",p->num);
     
     if(flag == 1)
        p = p->rchild;
     else
        p = p->lchild;
    }
}

TREE* convert(TREE* T)
{
  TREE* Last_node = NULL;
  convertnode( T, &Last_node);
  
  printf("Last_node is: %d\n",Last_node->num);
  Last_node->rchild = NULL;
  
  printf("revert list is:\n");
   print_list(Last_node,2);
  
  Last_node = find_head(T);
  printf("normal list is:\n");
  return Last_node;
}

int main(int argc, char *argv[])
{
  TREE* T = NULL;
  int num;
  int i;

  srand((unsigned int)time(NULL));
  for(i=0;i<MAX_NUM;i++)
   {
    num = rand()%100+1;
    add_tree(&T, num);
   }
  
  printf("mid walk tree is:\n");
  mid_walk(T);
  
  printf("\ndouble list is:\n");
  print_list(convert(T),1);
        
  system("PAUSE");
  return 0;
}