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

home_king

采用链栈来递归消除二叉树的先根遍历，我遇到了一点问题。
主要的算法还是比较传统：
1.构造一个链栈
2.while(当前树结点不为NULL)
{
访问当前结点
如果存在右子树，则将右子树结点指针入栈
如果左子树为NULL时，出栈，然后将出栈的结点指针替换为当前指针，继续下一个循环
替换当前树结点为其左子树
}

按这个算法来编写C代码，没有问题，但这个栈链究竟如何能弹出结点指针呢？换句话说，如何能改变传递给出栈函数的当前结点这个参数呢？

给出完整代码，大家帮我看看。

stack.h

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

复制代码

bitree.c

1. 
   
2. #include <stdlib.h>
   
3. #ifndef RECURSION
   
4. #include "stack.h"
   
5. #endif
   
6. 
   
7. typedef int datatype;
   
8. typedef struct node *pointer;
   
9. struct node
   
10. {
    
11.   datatype data;
    
12.   pointer lchild,rchild;
    
13. };
    
14. typedef pointer bitree;
    
15. 
    
16. bitree create_bitree (char Pre[],int ps,int pe,char In[],int is,int ie)
    
17. {
    
18.   bitree t;
    
19.   int i;
    
20.   if(ps>pe) return NULL;
    
21.   t=(bitree *)malloc(sizeof(bitree));
    
22.   t->data=Pre[ps];
    
23.   i=is;
    
24.   while(In[i]!=Pre[ps]) i++;
    
25.   t->lchild=create_bitree(Pre,ps+1,ps+i-is,In,is,i-1);
    
26.   t->rchild=create_bitree(Pre,ps+i-is+1,pe,In,i+1,ie);
    
27.   return t;
    
28. }
    
29. 
    
30. int free_bitree(bitree t)
    
31. {
    
32.   if(t->lchild==NULL && t->rchild==NULL) {
    
33.     free(t);
    
34.     return 1;
    
35.   }
    
36.   free_bitree(t->lchild);
    
37.   free_bitree(t->rchild);
    
38.   free(t);
    
39.   return 1;
    
40. }
    
41. 
    
42. #ifdef RECURSION
    
43. 
    
44. void list_bitree_rlr(bitree t)
    
45. {
    
46.   if(t==NULL) {
    
47.     printf("There is no data in this tree.\n");
    
48.     return 0;
    
49.   }
    
50.   if(t->lchild==NULL && t->rchild==NULL) {
    
51.     printf("%c ",t->data);
    
52.     return;
    
53.   }
    
54.   printf("%c ",t->data);
    
55.   list_bitree_rlr(t->lchild);
    
56.   list_bitree_rlr(t->rchild);
    
57. }
    
58. 
    
59. #else
    
60. 
    
61. void list_bitree_rlr(bitree t)
    
62. {
    
63.   lkstack mylkstack;
    
64.   /* DEBUG start */
    
65.   lkstack *debug=&mylkstack;
    
66.   /* DEBUG end */
    
67.   init_lkstack(&mylkstack);
    
68.   pointer p=t;
    
69.   while(p!=NULL){
    
70.     printf("%c ",p->data);
    
71.     if(p->rchild!=NULL) {
    
72.       push_lkstack(&mylkstack,p->rchild);
    
73.       /* DEBUG start */
    
74.       if (debug->top==NULL) printf("empty error.\n");
    
75.       printf("DEBUG tree -- %d\n",p->rchild);
    
76.       printf("DEBUG stack -- %d\n",debug->top->data);
    
77.       pop_lkstack(&mylkstack,p);
    
78.       printf("DEBUG pop node -- %d\n",p);
    
79.       return;
    
80.       /* DEBUG end */
    
81.     }
    
82.     if(p->lchild==NULL) {
    
83.       pop_lkstack(&mylkstack,p);
    
84.       continue;
    
85.     }
    
86.     p=p->lchild;
    
87.   }
    
88. }
    
89. 
    
90. #endif
    
91. 
    
92. main()
    
93. {
    
94.   bitree t;
    
95.   char Pre[6]="ABDEC";
    
96.   char In[6]="DBEAC";
    
97.   t=create_bitree(Pre,0,4,In,0,4);
    
98.   list_bitree_rlr(t);
    
99.   if(free_bitree(t)) printf("ok, the tree is free.\n");
    
100. }
     

复制代码

运行调试：

1. 
   
2. ibox@ibox ibox $ gcc -DRECURSION bitree.c
   
3. bitree.c: In function `create_bitree':
   
4. bitree.c:20: warning: assignment from incompatible pointer type
   
5. bitree.c: In function `list_bitree_rlr':
   
6. bitree.c:47: warning: `return' with a value, in function returning void
   
7. ibox@ibox ibox $ ./a.out
   
8. A B D E C ok, the tree is free.
   
9. ibox@ibox ibox $ gcc bitree.c
   
10. bitree.c: In function `create_bitree':
    
11. bitree.c:20: warning: assignment from incompatible pointer type
    
12. bitree.c: In function `list_bitree_rlr':
    
13. bitree.c:76: warning: passing arg 2 of `pop_lkstack' from incompatible pointer type
    
14. bitree.c:82: warning: passing arg 2 of `pop_lkstack' from incompatible pointer type
    
15. ibox@ibox ibox $ ./a.out
    
16. A DEBUG tree -- 134520976
    
17. DEBUG stack -- 134520976
    
18. *in stack* DEBUG -- 134520976
    
19. *in stack* DEBUG -- C
    
20. DEBUG pop node -- 134520912
    
21. ok, the tree is free.
    

复制代码

1.关键在于pop_lkstack这个函数不能把弹出的结点指针传递出去，导致死循环。
2.如果采用递归方式来遍历树，倒是没有问题的。
3.如果采用顺序栈，也不会出现问题。

ps：构造树的算法是采用先根遍历和中根遍历序列结合生成的

所以，整个算法是正确的，但错就错在C语言本身的指针规范，我不太清楚，大家指点。尤其是kj501兄，帮帮忙，谢谢。

yangtou

1. bitree.c: In function `create_bitree':
   
2. bitree.c:20: warning: assignment from incompatible pointer type
   

复制代码

1. bitree create_bitree (char Pre[],int ps,int pe,char In[],int is,int ie)
   
2. {
   
3.   bitree t;
   
4.   int i;
   
5.   if(ps>pe) return NULL;
   
6.   t=(bitree *)malloc(sizeof(bitree));

复制代码

yangtou

1. bitree.c: In function `list_bitree_rlr':
   
2. bitree.c:47: warning: `return' with a value, in function returning void
   

复制代码

1. void list_bitree_rlr(bitree t)
   
2. {
   
3.   if(t==NULL) {
   
4.     printf("There is no data in this tree.\n");
   
5.     return 0;
   
6.   }
   

复制代码

不要忽视任何warning

home_king

那些warnings和我说的问题是无关的。
我在上面用gcc -DRECURSION bitree.c来给出递归做法就是为了证实这个算法的正确性！

其实就是如何将指针传递出去的问题。

yangtou

1. typedef struct lkstack_node * lkstack_pointer

复制代码

1. int push_lkstack(lkstack *ls,lkstack_datatype x)
   
2. {
   
3.   lkstack_pointer p=malloc(sizeof(lkstack_pointer));
   

复制代码

home_king

最初由 yangtou 发表

1. typedef struct lkstack_node * lkstack_pointer

复制代码

1. int push_lkstack(lkstack *ls,lkstack_datatype x)
   
2. {
   
3.   lkstack_pointer p=malloc(sizeof(lkstack_pointer));
   

复制代码

压栈是没有问题的，请看debug调试输出部分。

yangtou

教主对指针和malloc的理解有误，我上面所说和第一个的waning显然是有问题的
再好好看看那些warning吧

1. warning: assignment from incompatible pointer type
   
2. bitree.c: In function `list_bitree_rlr':
   
3. bitree.c:47: warning: `return' with a value, in function returning void
   
4. ibox@ibox ibox $ ./a.out
   
5. A B D E C ok, the tree is free.
   
6. ibox@ibox ibox $ gcc bitree.c
   
7. bitree.c: In function `create_bitree':
   
8. bitree.c:20: warning: assignment from incompatible pointer type
   
9. bitree.c: In function `list_bitree_rlr':
   
10. bitree.c:76: warning: passing arg 2 of `pop_lkstack' from incompatible pointer type
    
11. bitree.c:82: warning: passing arg 2 of `pop_lkstack' from incompatible pointer type
    

复制代码

先把语法搞对，算法其实很简单，难搞的是语法

home_king

我想问的就是语法问题啊~~~
这个输出就是给大家看的。

兄弟能帮我修正吗？

yangtou

T* p=(T*)malloc(size)

home_king

最初由 yangtou 发表
T* p=(T*)malloc(size)

晕~~~
这个我知道阿。要不，递归算法也不会成功啊。

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

复制代码

请先看看我的代码好吗？或者帮忙调试一下也好啊。