关于二叉树的问题..请高手帮帮忙。.

m582445672

#include <stdio.h>
#include <stdlib.h>
typedef struct binode                          //线索定义....
{
char data ;
struct binode *lchild;                     //左孩子。...
struct binode *rchild;                 //右孩子...
int ltag;                                
int rtag;

} bithrnode ,*bithrtree ;



int inittree(bithrtree *t)                  //新键二叉树.....
{
char ch;
*t=(bithrtree )malloc(sizeof(bithrnode ));  //开空间.....
ch=getchar();                                  //输入结点......                             
(*t)->data=ch;
(*t)->lchild=NULL;                              
(*t)->rchild=NULL;                          //对左右子树..初始化...
     if(ch!=' ')
{
inittree(&(*t)->lchild);              //递归遍历二叉树....
inittree(&(*t)->rchild);
}
return 1;



}

int intreading(bithrtree *p,bithrnode *pre)    //线索化.......
{
if(*p)                                          
{
intreading(&(*p)->lchild,pre);          //中序线索化.....
if((*p)->lchild==NULL)                 //如果左孩子为空。.就连接前驱结点....               
{
(*p)->ltag=1;
(*p)->lchild=pre;

}
if(( pre)->rchild==NULL)             //如果右孩子为空。.就连接后续结点....
{
( pre)->rtag=1;
pre->rchild=*p;

}
pre=*p;                            //per指针。.跟上 p指针.....
intreading(&(*p)->rchild,pre);

}
return 1;


}



int InOrderThreading(bithrtree *p,bithrtree *thrt)         //线索化.......
{
bithrtree pre;                           

*thrt=(bithrtree )malloc(sizeof(bithrnode));  //开空间..
if(*thrt==NULL)
return 0;
(*thrt)->ltag=0;                   //右标志为0
(*thrt)->rtag=1;                      //右标志为1               
(*thrt)->rchild=*thrt ;              //右指针回指,,,,
if(p==NULL)
(*thrt)->lchild=*thrt;           //如果二叉树为空。.就左指针也回指..
else
{
(*thrt)->lchild=*p;              //如果不为空。. 就把。.根结点给头结点的左孩子。.
pre=*thrt;                     //pre指针。.指向头结点...
}
    intreading(p,pre);                  //调用过去..进行线索化...
(*thrt)->rtag=1;                  //最后一个结点的线索化....
pre->rchild=*thrt;
(*thrt)->rchild=pre;

return 1;



}


InOrderTraverse(bithrtree *t,bithrtree *thrt)       //二叉数输出...
{

*t=(*thrt)->lchild ;                  //头结点的左孩子给*t,,,,
while((*t)!=(*thrt))                //用来判断结束...  
{
while((*t)->ltag==0)            //如果没左孩子。..
{
*t=(*t)->lchild ;            //指向前驱。...
printf("%d %c %d\n",(*t)->ltag,(*t)->data,(*t)->rtag);


}
while((*t)->rtag==1&&(*t)->rchild!=*thrt)  //如果没有右孩子且最后一个结点不指向头结点.
{
*t=(*t)->rchild ;           //指向后续...
printf("%d %c %d\n",(*t)->ltag,(*t)->data,(*t)->rtag);


}
*t=(*t)->rchild;        //指针继续找后续。...不断变化，,,



}
return 1;




}



int main()
{
bithrtree a,thrt;  //thrt为结点

inittree(&a);
InOrderThreading(&a,&thrt);
InOrderTraverse(&a,&thrt);
return 1;

}


////////////////////////////////////////////////////////////////////////////


各位高手。.搞鸟这么多天。.还是没有搞定..真郁闷啊。.编译没有错。..就是输出没有结果。..郁闷啊..高手们..帮帮忙啊。..

m582445672

......忘说了。.这是二叉树的线索化...中序..线索...HELP..

cugb_cat

这样的问题还是自己慢慢调试吧～

MMMIX

原帖由 m582445672 于 2007-5-27 21:56 发表
#include <stdio.h>
#include <stdlib.h>
typedef struct binode                          //线索定义....
{
char data ;
struct binode *lchild;                     //左孩子。...
struct  ...

如果你不会或者不愿用调试器，那么就增加些打印语句吧。

hardboy_du

帮你格式化一下，感觉哥们是不是还是个学生

1. 
   
2. 
   
3. #include <stdio.h>
   
4. #include <stdlib.h>
   
5. typedef struct binode                          //线索定义....
   
6. {
   
7.         char data ;
   
8.         struct binode *lchild;                     //左孩子。...
   
9.         struct binode *rchild;                 //右孩子...
   
10.         int ltag;                                
    
11.         int rtag;
    
12. 
    
13. } bithrnode ,*bithrtree ;
    
14. 
    
15. 
    
16. 
    
17. int inittree(bithrtree *t)                  //新键二叉树.....
    
18. {
    
19.         char ch;
    
20.         *t=(bithrtree )malloc(sizeof(bithrnode ));  //开空间.....
    
21.         ch=getchar();                                  //输入结点......                             
    
22.         (*t)->data=ch;
    
23.         (*t)->lchild=NULL;                              
    
24.         (*t)->rchild=NULL;                          //对左右子树..初始化...
    
25.         if(ch!=' ')
    
26.         {
    
27.                 inittree(&(*t)->lchild);              //递归遍历二叉树....
    
28.                 inittree(&(*t)->rchild);
    
29.         }
    
30.         return 1;
    
31. }
    
32. 
    
33. int intreading(bithrtree *p,bithrnode *pre)    //线索化.......
    
34. {
    
35.         if(*p)                                          
    
36.         {
    
37.                 intreading(&(*p)->lchild,pre);          //中序线索化.....
    
38.                 if((*p)->lchild==NULL)                 //如果左孩子为空。.就连接前驱结点....               
    
39.                 {
    
40.                         (*p)->ltag=1;
    
41.                         (*p)->lchild=pre;
    
42.                 }
    
43.                 if(( pre)->rchild==NULL)             //如果右孩子为空。.就连接后续结点....
    
44.                 {
    
45.                         ( pre)->rtag=1;
    
46.                         pre->rchild=*p;
    
47.                 }
    
48.                 pre=*p;                            //per指针。.跟上 p指针.....
    
49.                 intreading(&(*p)->rchild,pre);
    
50. 
    
51.         }
    
52.         return 1;
    
53. }
    
54. 
    
55. 
    
56. 
    
57. int InOrderThreading(bithrtree *p,bithrtree *thrt)         //线索化.......
    
58. {
    
59.         bithrtree pre;                           
    
60. 
    
61.         *thrt=(bithrtree )malloc(sizeof(bithrnode));  //开空间..
    
62.         if(*thrt==NULL)
    
63.                 return 0;
    
64.         (*thrt)->ltag=0;                   //右标志为0
    
65.         (*thrt)->rtag=1;                      //右标志为1               
    
66.         (*thrt)->rchild=*thrt ;              //右指针回指,,,,
    
67.         if(p==NULL)
    
68.                 (*thrt)->lchild=*thrt;           //如果二叉树为空。.就左指针也回指..
    
69.         else
    
70.         {
    
71.                 (*thrt)->lchild=*p;              //如果不为空。. 就把。.根结点给头结点的左孩子。.
    
72.                 pre=*thrt;                     //pre指针。.指向头结点...
    
73.         }
    
74.         intreading(p,pre);                  //调用过去..进行线索化...
    
75.         (*thrt)->rtag=1;                  //最后一个结点的线索化....
    
76.         pre->rchild=*thrt;
    
77.         (*thrt)->rchild=pre;
    
78. 
    
79.         return 1;
    
80. }
    
81. 
    
82. 
    
83. InOrderTraverse(bithrtree *t,bithrtree *thrt)       //二叉数输出...
    
84. {
    
85. 
    
86.         *t=(*thrt)->lchild ;                  //头结点的左孩子给*t,,,,
    
87.         while((*t)!=(*thrt))                //用来判断结束...  
    
88.         {
    
89.                 while((*t)->ltag==0)            //如果没左孩子。..
    
90.                 {
    
91.                         *t=(*t)->lchild ;            //指向前驱。...
    
92.                         printf("%d %c %d\n",(*t)->ltag,(*t)->data,(*t)->rtag);
    
93.                 }
    
94.                 while((*t)->rtag==1&&(*t)->rchild!=*thrt)  //如果没有右孩子且最后一个结点不指向头结点.
    
95.                 {
    
96.                         *t=(*t)->rchild ;           //指向后续...
    
97.                         printf("%d %c %d\n",(*t)->ltag,(*t)->data,(*t)->rtag);
    
98.                 }
    
99.                 *t=(*t)->rchild;        //指针继续找后续。...不断变化，,,
    
100.         }
     
101.         return 1;
     
102. }
     
103. 
     
104. 
     
105. 
     
106. int main()
     
107. {
     
108.         bithrtree a,thrt;  //thrt为结点
     
109. 
     
110.         inittree(&a);
     
111.         InOrderThreading(&a,&thrt);
     
112.         InOrderTraverse(&a,&thrt);
     
113.         return 1;
     
114. 
     
115. }
     
116. 
     
117. 
     
118. ////////////////////////////////////////////////////////////////////////////
     
119. 
     

复制代码

[ 本帖最后由 hardboy_du 于 2007-5-28 09:02 编辑 ]

ken1984

真头痛，这种东西要自己写不管是谁都得花一定的时间去写和调试，而且完成的功能都一样，大家都在重复制造轮子。STD的出现也就不奇怪了。

MMMIX

原帖由 ken1984 于 2007-5-28 10:12 发表
真头痛，这种东西要自己写不管是谁都得花一定的时间去写和调试，而且完成的功能都一样，大家都在重复制造轮子。STD的出现也就不奇怪了。

学习的必经阶段罢了。

flw2

谁能说说线索化 有什么用，记得好像说是为了节省空间什么的

不过现实生活中没有见过。

justicezyx

线索化后放入数组保存，好处就是随机访问

softsongs

花点时间学习gdb，你不会后悔花时间在这个上面的。
光用肉眼看，至少我是看不出来的。