二叉树的先序非递归遍历皇星客栈

View Code
 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #define MAXNODE 100
 4 typedef int status;
 5 #define MAX 100
 6 
 7 typedef struct Bitree
 8 {
 9     struct Bitree *lchild;
10     struct Bitree *rchild;
11     char data;
12 }BiTree ,*BiTnode;
13 
14 BiTree *Create( )//建立二叉树
15 {
16     int i,j;
17     BiTree *root,*s,*Q[MAX];
18     char ch;
19     printf("请输入要建立的树的下标和数值:");
20    // getchar( );
21     scanf("%d %c",&i,&ch);
22     while(i!=0&&ch!='0')
23     {
24         s=(BiTree *)malloc(sizeof(BiTree));
25         s->data=ch;printf("%d%c*",i,ch);
26         s->lchild=NULL;
27         s->rchild=NULL;
28         Q[i]=s;
29         if(i==1)
30         root=s;
31         else
32         {
33             j=i/2;
34             if(i%2==0)
35                 Q[j]->lchild=s;
36             else
37                 Q[j]->rchild=s;
38         }
39         scanf("%d %c",&i,&ch);
40     }
41     return root;
42 }
43 
44 int  NRPreOrder(BiTnode bt)
45 {
46     BiTnode stack[MAXNODE],p;
47     int top;    //
48     if(bt==NULL)
49         return 1;
50     top=-1;
51     p=bt;
52 
53     while(!(p==NULL&&top==-1)){
54     while(p!=NULL){//printf("*");
55         printf("%c ",p->data);
56         if(top<MAXNODE-1){
57             top++;
58             stack[top]=p;
59             }
60         else{
61             printf("wrong\n");
62             return 0;
63         }
64     p=p->lchild;
65    }
66    if(top==-1)
67         return 1;
68    else{
69        p=stack[top];
70        top--;
71        p=p->rchild;
72    }
73   }
74 }
75 
76 
77 int main( )
78 {
79     BiTnode Bt;
80     Bt=Create( );
81     printf("\n");
82     NRPreOrder(Bt);
83     return 0;
84 }
二叉树的先序非递归遍历 皇星客栈

二叉树的先序非递归遍历皇星客栈
