C 二叉树的建立，遍历（递归，非递归）

1. #include<stdio.h>  
2. #include<stdlib.h>  
3.  
4. #define MAXSIZE 20  
5.  
6. typedef struct BiTnode{  
7.  char data;  
8.  struct BiTnode *lchild,*rchild;  
9. }BiTnode,*BiTree;  
10.  
11.  
12. //浜屽弶鏍戠殑閫掑綊寤虹珛  
13. int i = 0;  
14. BiTree Create(BiTree t,char s[])  
15. {  
16.  char ch;  
17.  ch = s[i++];  
18.    
19.  if(ch == ' ')  
20.  {  
21.   t = NULL;  
22.  }  
23.  else 
24.  {  
25.   if(!(t = (BiTree)malloc(sizeof(BiTnode))))  
26.   {  
27.    printf("fail to malloc!\n");  
28.    exit(0);  
29.   }  
30.   else 
31.   {  
32.    t->data = ch;  
33.    t->lchild = Create(t->lchild,s);  
34.    t->rchild = Create(t->rchild,s);  
35.   }  
36.  }  
37.  return t;  
38. }  
39.  
40.    
41.  
42. //涓簭閬嶅巻  
43. /*  
44. void display(BiTree t)  
45. {  
46.  BiTree stack[MAXSIZE],p;  
47.  int top = -1;  
48.  if(t)  
49.  {  
50.   p = t;  
51.   while(top > -1 || p)  
52.   {  
53.    while(p)  
54.    {      
55.     stack[++top] = p;  
56.     p = p->lchild;   
57.    }   
58.    if(top > -1)  
59.    {  
60.     p = stack[top--];      
61.     printf("%c ",p->data);  
62.     p = p->rchild;   
63.    }  
64.   }  
65.   printf("\n");  
66.  }  
67. }  
68. /*/ 
69.  
70.    
71.  
72. //鍓嶅簭閬嶅巻  
73. /*  
74. void display(BiTree t)  
75. {  
76.  BiTree stack[MAXSIZE],p;  
77.  int top = -1;  
78.  if(t)  
79.  {  
80.   p = t;  
81.   while(top > -1 || p)  
82.   {  
83.    while(p)  
84.    {   
85.     printf("%c ",p->data);     
86.     stack[++top] = p;  
87.     p = p->lchild;   
88.    }   
89.    if(top > -1)  
90.    {  
91.     p = stack[top--];          
92.     p = p->rchild;  
93.       
94.    }  
95.   }  
96.   printf("\n");  
97.  }  
98. }  
99.  
100. *//*  
101.    
102.  
103.  
104. //鍓嶅簭閬嶅巻  
105. void display(BiTree t)  
106. {  
107.      BiTree stack[MAXSIZE], p;  
108.      int top = -1;  
109.      if (t)  
110.      {          
111.          stack[++top] = t;  
112.          while (top > -1)  
113.          {                
114.              p = stack[top--];  
115.              printf("%c ", p->data);                
116.              if (p->rchild)  
117.               {                    
118.                   stack[++top] = p->rchild;  
119.               }                
120.              if (p->lchild)  
121.               {                   
122.                   stack[++top] = p->lchild;  
123.               }  
124.          }  
125.          printf("\n");  
126.      }  
127. }*/ 
128.  
129. /*  
130.  
131. //闈為€掑綊鍚庡簭閬嶅巻  
132.  
133. void display(BiTree t)  
134. {  
135.  BiTree m,stack[MAXSIZE];  
136.  int top = -1;  
137.  int flag;   
138.  
139.  if(t)  
140.  {  
141. loop:  
142.   flag = 1;  
143.   m = NULL;  
144.   while(t)  
145.   {  
146.    stack[++top] = t;  
147.    t = t->lchild;  
148.   }  
149.   while(flag)  
150.   {  
151.    t = stack[top];  
152.    if(t->rchild == m)  
153.    {  
154.     printf("%c ",t->data);  
155.     top--;  
156.     m = t;  
157.    }  
158.    else  
159.    {  
160.     flag = 0;  
161.     t = t->rchild;  
162.    }  
163.   }  
164.   if(top>-1)  
165.    goto loop;  
166.  }  
167.    
168.  printf("\n");  
169. }  
170.  
171. */ 
172.  
173.    
174.  
175. //闈為€掑綊鍚庡簭閬嶅巻  
176. void display(BiTree t)  
177. {  
178.     BiTree p = t, stack[MAXSIZE];   
179.     int tag[MAXSIZE];  
180.     int top = -1;  
181.       
182.  do 
183.      {  
184.          while(p != NULL)   
185.          {  
186.              stack[++top] = p;  
187.              tag[top] = 0;  
188.              p = p->lchild;  
189.          }               
190.          if(top > -1)   
191.          {  
192.              if(!tag[top])    
193.               {  
194.                   p = stack[top];   
195.                   p = p->rchild;   
196.                   tag[top] = 1;   
197.               }  
198.              else   
199.               {              
200.                    printf("%c ", stack[top--]->data);   
201.               }  
202.          }  
203.      }while((p != NULL)||(top > -1));  
204.  printf("\n");  
205. }       
206.  
207.  
208. //閫掑綊鍓嶅簭閬嶅巻  
209. /*void display(BiTree t)  
210. {  
211.  if(t)  
212.  {  
213.   printf("%c ",t->data);  
214.   display(t->lchild);  
215.   display(t->rchild)锛?  
216.  }  
217. }*/ 
218.  
219. //閫掑綊涓簭閬嶅巻  
220. /*void display(BiTree t)  
221. {  
222.  if(t)  
223.  {  
224.   display(t->lchild);  
225.   printf("%c ",t->data);  
226.   display(t->rchild)锛?  
227.  }  
228. }*/ 
229.  
230.  //閫掑綊鍚庡簭閬嶅巻  
231. /*void display(BiTree t)  
232. {  
233.  if(t)  
234.  {  
235.     
236.   display(t->lchild);  
237.   display(t->rchild);  
238.   printf("%c ",t->data);  
239.  }  
240. }*/ 
241.  
242. int main(int argc,char *argv[])  
243. {  
244.  BiTree t;  
245.  char s[] = "abc  de f  g    ";  
246.  t = Create(t,s);  
247.  display(t);  
248.    
249.  return 0;  
250. }  
251.    

     本文转自 驿落黄昏 51CTO博客，原文链接：http://blog.51cto.com/yiluohuanghun/631727，如需转载请自行联系原作者