偶这星期刚学完树这章,写个二叉树遍历的完整程序共同学习一下吧 ^_^

 

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

 

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

 

typedef int SElemType;
typedef struct
{
   SElemType *base;
   SElemType *top;
   int stacksize;
}Stack;

 

void InitStack(Stack &s){

   s.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
   if (!s.base) printf("failed!");
   s.top=s.base;
   s.stacksize=STACK_INIT_SIZE;
}

 

bool StackEmpty(Stack &s){
 
 if(s.top==NULL)
  return true;
 return false;

}

 

void push(Stack &s,SElemType &e)
  {
 if(s.top-s.base>=s.stacksize)
 {
  s.base=(SElemType *)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(SElemType));
     if(s.base) printf("failed!");
     s.top=s.base+s.stacksize;
     s.stacksize+=STACKINCREMENT;
 }
 *s.top=e;
 s.top++;

  }

 

SElemType pop(Stack &s,SElemType &e)
  {if(s.top==s.base) printf("empty stack now!");
  e=*(s.top-1);
  return e;
  }

void Visit(int data){

 printf("%c->",data);
}

 

typedef int TelemType;
typedef struct BiTNode{

 TelemType data;
 struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

 

BiTree CreateBiTree() {
 BiTree T;
    char ch;
    scanf("%c", &ch);
    getchar();
    if(ch=='@') T=NULL;
    else {
         if(!(T= (BiTNode*)malloc(sizeof(struct BiTNode)))) printf("OverFlow\n");
        T->data=ch;
  printf("请给%c的左子树赋值",ch);
  T->lchild=CreateBiTree();
  printf("请给%c的右子树赋值",ch);
  T->rchild=CreateBiTree();
    }
    return T;
}

 

void PreOrderTraverse(BiTree t)
{
    Stack s;
    InitStack(s);
    BiTree p=t;
   
    while (p||!StackEmpty(s))
    {
        while (p)
        {
            Visit(p->data);
            push(s,p->data);
            p=p->lchild;      
        }
       
        if (!StackEmpty(s))
        {
            pop(s,p->data);
            p=p->rchild;       
        }
               
    }
   
}

void main()
{

 printf("通过输入给二叉树初始化,当输入'@'时该结点为叶结点即没有子孙\n");
 printf("请输入根节点:");
 BiTree T=CreateBiTree();
 PreOrderTraverse(T);
 putchar('\n');
}