1 #include <stdio.h> 2 #include <stdlib.h> 3 #define MAX  10 4  5  6 //二叉树存储结构定义 7 typedef char Item; 8 typedef struct node *link; 9 struct node {Item item; link l, r;};10 11 int  Create(link *tp);12 void show(link h);13 void tranverse(link h, void (*visit)(link));14 15 //下推栈存储结构定义16 typedef link SItem;17 static SItem *s;18 static int    N;19 20 void  STACKinit(int maxN);21 int   STACKempty();22 void  STACKpush(SItem item);23 SItem STACKpop();24 25 26 int main()27 {28     link tree;29 30     Create(&tree);31     tranverse(tree, show);32 33     return 0;34 }35 36 void STACKinit(int maxN)37 {38     s = (SItem *)malloc(maxN * sizeof(SItem));39     if (!s) return;40     N = 0;41 }42 43 int STACKempty()44 {45     return N==0;46 }47 48 void STACKpush(SItem item)49 {50     s[N++] = item;51 }52 53 SItem STACKpop()54 {55     return s[--N];56 }57 58 int Create(link *tp)59 {60     //构造方法，或者说构造顺序：中序遍历构造61     char x;62     scanf("%c",&x);63     if(x==‘#‘)64     {65         *tp=NULL;//指针为空，树节点中的某个指针为空66         return 0;67     }68     *tp=(link)malloc(sizeof(**tp));//将树节点中指针指向该地址空间69     if(*tp==NULL)70         return 0;71     (*tp)->item=x;72     Create(&((*tp)->l));73     Create(&((*tp)->r));74     return 1;75 }76 77 void show(link h)78 {79     printf(" %c ", h->item);80 }81 82 //前序遍历83 void tranverse(link h, void (*visit)(link))84 {85     STACKinit(MAX);86     STACKpush(h);87     while (!STACKempty()){88         (*visit)(h = STACKpop());89         if (h->r != NULL) STACKpush(h->r);90         if (h->l != NULL) STACKpush(h->l);91     }92 }