二叉树的递归以及非递归调用

  回家前，XT给了个二叉树的wiki链接。很长很长的代码,然后批评了下我的二叉树写的如此之简单,惭愧惭愧。也接受批评。最近blog承蒙兄弟姐妹们抬举，特别是XT,梅总提出一些错误^_^,这里感谢下。当然还有那些至今都没留下过脚印的兄弟姐妹们。

  修改下月之女祭司的话Warriors  of IT, assemble!!!^_^.

  其实二叉树主要就是个创建,遍历(前,中，后，层),求最小一直lchild，最大一直rchild。高度复杂点。删除一个节点，难得写^_^.我blog里应该有每次都是删除最小的那个的。好了，进入正题。这次只是放出前，中，后遍历递归以及非递归的版本。层序的，我blog之前谢过了

#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 stack
{
 int top;
 TREE* tree[N];
}STACK;

STACK* init_stack()
{
  int i;
  STACK* S = (STACK*)malloc(sizeof(STACK));
  S->top = 0;
  for(i=0;i<N;i++)
   S->tree[i] = 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 preorder(TREE* T)
{
  if(T!=NULL)
   {
     printf("%d ",T->num);
     preorder(T->lchild);
     preorder(T->rchild);
   }
}

void preorder_no_rec(TREE* T, STACK* S)
{
   while(T!=NULL || !s_empty(S))
   {
     if(T!=NULL)
      {
        printf("%d ",T->num);
        s_push(T, S);
        T = T->lchild;
      }
     else
      {
        T = s_pop(S);
        T = T->rchild;
      }
   }
}
    
void midorder(TREE* T)
{
  if(T!=NULL)
   {
     midorder(T->lchild);
     printf("%d ",T->num);
     midorder(T->rchild);
   }
}

void midorder_no_rec(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);
        printf("%d ",T->num);
        T = T->rchild;
      }
   }
}

void postorder(TREE* T)
{
  if(T!=NULL)
   {
     postorder(T->lchild);
     postorder(T->rchild);
     printf("%d ",T->num);
   }
}

void postorder_no_rec(TREE* T, STACK* S)
{
  if( T!=NULL )
    s_push(T,S);
  while(!s_empty(S))
   {
     T = s_pop(S);
     if(T->num&0x80)
        printf("%d ",T->num & 0x7F);
     else
      {
        s_push(T,S);
        if(T->rchild != NULL)
          s_push(T->rchild,S);
        if(T->lchild != NULL)
          s_push(T->lchild,S);
      }
      T->num = T->num | 0x80;
   }
}

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;i<N;i++)
   {
     num = get_rand( A, i, N-1);
     add_tree( &T, num);
   }
  printf("the array is:\n");
  for(i=0;i<N;i++)
    printf("%d ",A[i]);
  
  STACK* S = init_stack();
  printf("\npre order:\n");
  printf("\n\t\t rec \t\t\n");
  preorder(T);
  printf("\n\t\t no rec \t\t\n");
  preorder_no_rec(T,S);
    
  printf("\nmid order:\n");
  printf("\n\t\t rec \t\t\n");
  midorder(T);
  printf("\n\t\t no rec \t\t\n");
  midorder_no_rec(T,S);
  
  printf("\npost order:\n");
  printf("\n\t\t rec \t\t\n");
  postorder(T);
  printf("\n\t\t no rec \t\t\n");
  postorder_no_rec(T,S);
  printf("\n");
    
  system("PAUSE");    
  return 0;
}