关于采用链栈实现递归消除二叉树的遍历

yangtou

这是我修改出的

1. //stack.h
   
2. #include <stdlib.h>
   
3. /* Store per pointer of bitree */
   
4. typedef void * lkstack_datatype;
   
5. typedef struct lkstack_node * lkstack_pointer;
   
6. struct lkstack_node
   
7. {
   
8.   lkstack_datatype data;
   
9.   lkstack_pointer next;
   
10. };
    
11. typedef struct
    
12. {
    
13.   lkstack_pointer top;
    
14. } lkstack;
    
15. 
    
16. /* functions for lkstack */
    
17. int push_lkstack(lkstack *ls,lkstack_datatype x)
    
18. {
    
19.   lkstack_pointer p=(lkstack_pointer)malloc(sizeof(struct lkstack_node));
    
20.   p->data=x;
    
21.   p->next=ls->top;
    
22.   ls->top=p;
    
23.   return 1;
    
24. }
    
25. 
    
26. int pop_lkstack(lkstack *ls, lkstack_datatype [color=orange]*x[/color] )
    
27. {
    
28.   lkstack_pointer p;
    
29.   if(ls->top==NULL) return 0;
    
30.   p=ls->top;
    
31.   [color=orange]*x=p->data;[/color]
    
32.   ls->top=p->next;
    
33.   free(p);
    
34.   return 1;
    
35. }
    
36. 
    
37. void init_lkstack(lkstack *ls)
    
38. {
    
39.   ls->top=NULL;
    
40. }
    

复制代码

1. //bitree.c
   
2. #include <stdlib.h>
   
3. #include "stack.h"
   
4. typedef int datatype;
   
5. typedef struct node *pointer;
   
6. struct node
   
7. {
   
8.   datatype data;
   
9.   pointer lchild,rchild;
   
10. };
    
11. typedef pointer bitree;
    
12. bitree create_bitree (char Pre[],int ps,int pe,char In[],int is,int ie)
    
13. {
    
14.   bitree t;
    
15.   int i;
    
16.   if(ps>pe) return NULL;
    
17.   t=(bitree)malloc(sizeof(struct node));
    
18.   t->data=Pre[ps];
    
19.   i=is;
    
20.   while(In[i]!=Pre[ps]) i++;
    
21.   t->lchild=create_bitree(Pre,ps+1,ps+i-is,In,is,i-1);
    
22.   t->rchild=create_bitree(Pre,ps+i-is+1,pe,In,i+1,ie);
    
23.   return t;
    
24. }
    
25. int free_bitree(bitree t)
    
26. {
    
27.   if(t->lchild==NULL && t->rchild==NULL) {
    
28.     free(t);
    
29.     return 1;
    
30.   }
    
31.   free_bitree(t->lchild);
    
32.   free_bitree(t->rchild);
    
33.   free(t);
    
34.   return 1;
    
35. }
    
36. void list_bitree_rlr(bitree t)
    
37. {
    
38.   lkstack mylkstack;
    
39.   /* DEBUG start */
    
40.   lkstack *debug=&mylkstack;
    
41.   /* DEBUG end */
    
42.   init_lkstack(&mylkstack);
    
43.   [color=orangered] push_lkstack(&mylkstack,NULL);//在栈底放置NULL指针[/color]
    
44.   pointer p=t;
    
45.   while(p!=NULL){
    
46.     printf("%c ",p->data);
    
47.     if(p->rchild!=NULL) {
    
48.       push_lkstack(&mylkstack,p->rchild);
    
49.     }
    
50.     if(p->lchild==NULL) {
    
51.       pop_lkstack(&mylkstack,(void*)&p);
    
52.       continue;
    
53.     }
    
54.     p=p->lchild;
    
55.   }
    
56. }
    
57. main()
    
58. {
    
59.   bitree t;
    
60.   char Pre[6]="ABDEC";
    
61.   char In[6]="DBEAC";
    
62.   t=create_bitree(Pre,0,4,In,0,4);
    
63.   list_bitree_rlr(t);
    
64.   if(free_bitree(t)) printf("ok, the tree is free.\n");
    
65. }
    

复制代码

yangtou

教主所有的malloc用法都是错误的T* p = (T*)malloc(...)虽然你用递归方法是成功了，但那确实是错误的

另一个问题是

1. int pop_lkstack(lkstack *ls, lkstack_datatype *x)
   
2. {
   
3.   lkstack_pointer p;
   
4.   if(ls->top==NULL) return 0;
   
5.   p=ls->top;
   
6.   x=p->data;        //[color=orange]//改为*x=p->data[/color]  
   
7. /* DEBUG start */
   
8.   printf("*in stack* DEBUG -- %d\n",p->data);
   
9.   printf("*in stack* DEBUG -- %c\n",*x);
   
10.   /* DEBUG end */
    
11.   ls->top=p->next;
    
12.   free(p);
    
13.   return 1;
    
14. }
    

复制代码

调用时也要做相应修改

还有前序遍历二叉树要在栈底放个NULL指针

kj501

我看到的问题，yangtou兄都已经指出来了。此外，教主的编码风格我觉得怪怪的，如：

1. #ifndef RECURSION
   
2. #include "stack.h"
   
3. #endif
   

复制代码

如果只是为了避免重复包含头文件，通常的做法是用：

1. 
   
2. #ifndef STACK_H
   
3. #define STACK_H
   
4. ....
   
5. #endif
   

复制代码

这样就没有必要在命令行输入一个-DRECURSION这样的参数来防止头文件重复包含了。
还有一个是习惯问题。如：

1. 
   
2. typedef struct node *pointer;
   

复制代码

一般typedef定义的类型最好首字母大写。如：

1. 
   
2. typedef struct node *Pointer;
   

复制代码

这样容易在阅读代码时与定义的变量区分开来，方便他人阅读代码，自己在编码时也减少犯错误的机会。

home_king

呵呵，谢谢各位兄弟。问题解决了。

主要是因为我很久没有接触C了，对它的语法都忘得差不多。目前还只熟悉数据结构和算法而已。

yangtou兄和我的作法最大的不同在于：

1. 
   
2. pop_lkstack(&mylkstack,p); [color=green][b]#我的作法[/b][/color]
   
3. pop_lkstack(&mylkstack,[color=red][b](void*)&p[/b][/color]); [color=green][b]#yangtou兄的修正[/b][/color]
   

复制代码

这就使得pop_lkstack能把弹出的结点指针值传递出去了。

谢谢yangtou，使我深化了如何使用栈链来操作指针类型的栈成员。可以进一步解释一下为什么吗？

至于malloc，我想我就是将指针和结构体混淆了。

to kj501兄：
关于按需包含头文件，好象按照
#ifdef STACK_H
#define STACK_H
#endif
来做不行阿。反而像我这样做倒是可以，虽然我不知道规不规范。

yangtou

1. typedef struct lkstack_node * lkstack_pointer

复制代码

1. lkstack_pointer p=malloc(sizeof(lkstack_pointer));
   
2. bitree t;
   
3. t=(bitree *)malloc(sizeof(bitree));
   

复制代码

lkstack_pointer是指向lkstack_node的指针，所以应该是lkstack_pointer p =(lkstack_pointer)malloc(sizeof(lkstack_node))

T* p=(T*)malloc(sizeof(T))

home_king

另外，可以看到简单的这样一个头文件，如果疏忽，都会犯命名冲突的错误。
C语言本身不包含命名冲突解决机制，这是很头痛的事情，要是项目大了，那么按照section1_section2_section3_...sectionN来命名，那岂不是很烦。

yangtou

最初由 home_king 发表
呵呵，谢谢各位兄弟。问题解决了。

主要是因为我很久没有接触C了，对它的语法都忘得差不多。目前还只熟悉数据结构和算法而已。

yangtou兄和我的作法最大的不同在于：

1. 
   
2. pop_lkstack(&mylkstack,p); [color=green][b]#我的作法[/b][/color]
   
3. pop_lkstack(&mylkstack,[color=red][b](void*)&p[/b][/color]); [color=green][b]#yangtou兄的修正[/b][/color]
   

复制代码

看看我改的代码中加色的部分

home_king

最初由 yangtou 发表
看看我改的代码中加色的部分

我知道，你这样做是为了使指针类型匹配(栈链弹出函数的实参和形参类型一致)，只是不清楚C的具体表示语法而已。

另外，没有必要在栈链初始化后就压入NULL，因为栈链有top指针来指示栈链顶部，而且这个top在初始化时也置为NULL。yangtou兄试试看。

ps：我发现自己的表达能力有点差。。。。大家帮忙时总是兜了圈子

yangtou

两个NULL是不一样的，你再仔细看看

我现在有事不能上网了，88

home_king

最初由 yangtou 发表
两个NULL是不一样的，你再仔细看看

我现在有事不能上网了，88

我想实在是没必要用的。

很简单，去掉你这行代码，对结果没有影响。除非还有什么别的安全含意。