百度笔试题之二叉树叶子节点链接

ubuntuer

   二叉树的叶子节点，从左到右把叶子节点链接起来
   我这里理解为就是把二叉树按层遍历,给链表链接起来...觉得这题还是比较NX的,考到了二叉树,队列和链表。如果是求所有的叶子节点的话,我程序里面只用加一条语句
   
  
#include stdio.h>
#include stdlib.h>
#include stdlib.h>
#define MAX_NUM 20
#define MAX_VALUE 100
static int count = 0;
typedef struct tree
{
   int num;
   struct tree* parent;
   struct tree* lchild;
   struct tree* rchild;
}TREE;
typedef struct queue
{
int front;
int rear;
TREE** tree;
}QUEUE;
typedef struct list
{
   TREE* tree;
   struct list* next;
}LIST;

int getrand()
{
   return rand()%MAX_VALUE+1;
    }
void en_queue(QUEUE* Q,TREE* T)
{
    if((Q->rear + 1)%MAX_NUM ==Q->front)
     {
      printf("full\n");
      return;
     }
    Q->tree[Q->rear] = T;
    if(++(Q->rear)==MAX_NUM)
      Q->rear = 0;
}
   
TREE* de_queue(QUEUE* Q)
{
   TREE* tree = NULL;
  if(Q->front == Q->rear)
    return NULL;
   
  tree = Q->tree[Q->front];
   
  if(++(Q->front)==MAX_NUM)
      Q->front = 0;
         
    return tree;
}
  
int init_list(LIST** L)
{
  *L = (LIST*)malloc(sizeof(LIST));
  (*L)->next = NULL;
}
   
int tree_add(TREE** T,TREE* parent,int num)
{
   if(*T == NULL)
    {
       printf("add %d\n",num);
       *T = (TREE*)malloc(sizeof(TREE));
      (*T)->num = num;
      (*T)->parent = parent;
      (*T)->lchild = NULL;
      (*T)->rchild = NULL;
      return 0;
     }
    else if((*T)->num = num)
     return tree_add(&((*T)->rchild),*T,num);
    else
     return tree_add(&((*T)->lchild),*T,num);
}
int init_tree(TREE** T)
{
  int i= 0;
  int num;
  srand((unsigned)time(NULL));
  for(;iMAX_NUM;i++)
   {
    num = getrand();
    tree_add(T, NULL, num);
  }
  return 0;
}
void walk_tree(TREE* T)
{
  if(T!=NULL)
   {
    walk_tree(T->lchild);
    if(++count%5==0)
     printf("%d\n",T->num);
    else
     printf("%d\t",T->num);
    walk_tree(T->rchild);
  }
}
void pre_walk_tree(TREE* T)
{
  if(T!=NULL)
   {
    if(++count%5==0)
     printf("%d\n",T->num);
    else
     printf("%d\t",T->num);
    walk_tree(T->lchild);
    walk_tree(T->rchild);
  }
}
void print_list(LIST* L)
{
   LIST* p = L->next;
   count = 0;
   while(p!=NULL)
    {
     if(++count%5 ==0)
       printf("%d\n",p->tree->num);
     else
       printf("%d\t",p->tree->num);
     
     p = p->next;
     }
}

int layer_walk_tree(TREE* T,QUEUE* Q,LIST* L)
{
  LIST* p = L;
  count = 0;
  while(T!=NULL)
  {
   
   if(++count%5 == 0)
     printf("%d\n",T->num);
   else
     printf("%d\t",T->num);
  
  /***如果是要求叶子节点的话
   ***   if((T->lchild == NULL)&&(T->rchild == NULL))
   ***
  *********/
   LIST* q = (LIST*)malloc(sizeof(LIST));
   q->tree = T;
   q->next = p->next;
   p->next = q;
   p = q;
  
   if(T->lchild != NULL)
     en_queue(Q,T->lchild);
   
   if(T->rchild != NULL)
     en_queue(Q,T->rchild);
     
    T = de_queue(Q);
   }
   
   return 0;
}
void free_mem(QUEUE* Q,LIST* L)
{
  int i = 0;
  for(;iMAX_NUM;i++)
   free(Q->tree);
  free(Q);
  
  LIST* p = L->next;
  LIST* q = L->next;
  while(p!=NULL)
  {
     q = p->next;
     free(p->tree);
     free(p->next);
     p = q;
   }
   free(L);
}

int main(int argc, char *argv[])
{
  TREE* T = NULL;
  QUEUE* Q = (QUEUE*)malloc(sizeof(QUEUE));
  Q->front = 0;
  Q->rear = 0;
  Q->tree = (TREE**)malloc(sizeof(TREE)*MAX_NUM);
  
  LIST* L = NULL;
  init_list(&L);
   
  init_tree(&T);
  printf("begin mid walk tree\n");
  walk_tree(T);
  printf("\nend mid walk tree\n");
  
  printf("begin pre walk tree\n");
  pre_walk_tree(T);
  printf("\nend pre walk tree\n");
  
  layer_walk_tree(T,Q,L);
  
  printf("begin print list tree\n");
  print_list(L);
  printf("\nend print list tree\n");
  
  free_mem(Q,L);
  
  system("PAUSE");   
  return 0;
}


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