二叉树

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

#define MAXSTACK 20

typedef char elemtype;
typedef struct btnode
{
  elemtype data;
  struct btnode *lchild,*rchild;
} bitnode,*bitree;

// 创建二叉树

int creatbitree(bitree *t, int level)
{
  char ch;
  printf(">");
  scanf("%c",&ch);
  getchar();
  if(ch=='#')
  {
     (*t)=NULL;
     return 0;
  }
  else
  {
     (*t)=(bitnode*)malloc(sizeof(bitnode));
     (*t)->data=ch;
     printf("enter %d left child\n",level);
     creatbitree1(&(*t)->lchild,level+1);
     printf("enter %d right child\n",level);
     creatbitree1(&(*t)->rchild,level+1);
  }
  return 0;
}

// 非递归前序遍历二叉树

void preorder(bitree p)
{
   bitree stack[MAXSTACK];
   int top = 0;
   
   while(p!=NULL||top!=0)
   {
      if(p!=NULL)
      {
         printf("%c\n",p->data);
         stack[top++]=p;
         p=p->lchild; //遍历左子树

      }
      else
      {
          p=stack[--top];
          p=p->rchild; //遍历右子树

      }
   }
}

// 非递归中序遍历二叉树

void midorder(bitree t)
{
  bitree tmp = NULL;
  // 保存节点的栈

  bitree stack[MAXSTACK];
  int top = 0;
  
  memset(stack, 0x00, sizeof(stack));

  tmp = t;

  while((tmp != NULL) || (top > 0))
  {
     if (tmp != NULL)
     {
        stack[top++] = tmp;
        tmp = tmp->lchild;
     }
     else
     {
        tmp = stack[--top];
        printf("%c\n", tmp->data);
        tmp = tmp->rchild;
     }
  }
}

int main(int argc, char *argv[])
{
  bitree t;//=creatbitree();

  creatbitree1(&t,0);
  
  printf("++++++++++++++++++++\n");
  midorder(t);
  preorder(t);
  
  return 0;
}