二叉树的叶子节点，从左到右把叶子节点链接起来

ubuntuer

  其实跟中序遍历一样,其实任何遍历都差不多!!我这里使用中序遍历

#include stdio.h>
#include stdlib.h>
#include time.h>
#define N 10
typedef struct tree
{
  int num;
  struct tree* lchild;
  struct tree* rchild;
}TREE;
typedef struct list
{
  TREE* tree;
  struct list* next;
}LIST;
typedef struct stack
{
int top;
TREE* tree[N];
}STACK;
STACK* init_stack()
{
  int i;
  STACK* S = (STACK*)malloc(sizeof(STACK));
  S->top = 0;
  for(i=0;iN;i++)
   S->tree = NULL;
  return S;
}
void s_push(TREE* T,STACK* S)
{
  S->tree[S->top] = T;
  (S->top)++;
}
TREE* s_pop(STACK* S)
{
  (S->top)--;
  return S->tree[S->top];
}
int s_empty(STACK* S)
{
  if(S->top == 0)
    return 1;
  else
    return 0;
}
void swap( int* a, int* b)
{
  int tmp = *a;
  *a = *b;
  *b = tmp;
}
int get_rand( int A[], int start, int end)
{
   int num = rand()%(end - start + 1) + start;
   swap(A+num, A+start);
   return A[start];
}
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)
      add_tree( &((*T)->lchild), num);
    else
      add_tree( &((*T)->rchild), num);
}
void add_list_tail(LIST* L, TREE* T)
{
  LIST* p = L->next;
  LIST* q = L;
  
  while(p!=NULL)
   {
    q = p;
    p = p->next;
   }
  p = (LIST*)malloc(sizeof(LIST));
  p->tree = T;
  p->next = NULL;
  q->next = p;
}
void link_leaf(LIST* L, TREE* T, STACK* S)
{
  while(T!=NULL || !s_empty(S))
   {
     if(T!=NULL)
      {
        s_push(T, S);
        T = T->lchild;
      }
     else
      {
        T = s_pop(S);
        if(T->lchild==NULL&&T->rchild==NULL)
          add_list_tail(L, T);
         
        //printf("%d ",T->num);
        T = T->rchild;
      }
   }
}
void print_list(LIST* L)
{
  LIST* p = L->next;
  while(p!=NULL)
   {
     printf("%d\t", p->tree->num);
     p = p->next;
   }
   printf("\n");
}
int main(int argc, char *argv[])
{
  TREE* T = NULL;
  
  int i;
  int num;
  int A[N] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  srand((unsigned int)time(NULL));
  for(i=0;iN;i++)
   {
     num = get_rand( A, i, N-1);
     add_tree( &T, num);
   }
  printf("the array is:\n");
  for(i=0;iN;i++)
    printf("%d ",A);
  printf("\n");
  STACK* S = init_stack();
  LIST* L = (LIST*)malloc(sizeof(LIST));
  L->next = NULL;
  
  link_leaf(L, T, S);
  
  print_list(L);
  system("PAUSE");   
  return 0;
}


本文来自ChinaUnix博客，如果查看原文请点：http://blog.chinaunix.net/u2/76292/showart_2063226.html