二叉树遍历递归函数用法，有点不懂,求指点

漠水

这里的visit函数为什么能直接显示左孩子和右孩子的int值，这里没有用t->l->n表示，难道这样默认也行？

1. void visit (int e)
   
2. { printf("%d ",e);
   
3. }
   
4. 
   
5. void bianli(tree *t,void(*visit)(int)) //函数定义调用函数 需将类型报出，然后用指针*调用
   
6. {
   
7. if(t!=NULL)
   
8. {
   
9. printf("%d ",t->n);
   
10. bianli(t->l,visit); //left左孩子
    
11. bianli(t->r,visit); //right右孩子
    
12. 
    

复制代码

下面是全部代码

1. #include<stdio.h>
   
2. #include<malloc.h>
   
3. #define NULL 0
   
4. 
   
5. typedef struct tree
   
6. {
   
7. int n;
   
8. struct tree *l ,*r,*p; //l 表示左孩子 r 表示右孩子 p表示父亲
   
9. 
   
10. }tree;
    
11. 
    
12. 
    
13. tree *gen()
    
14. {
    
15. tree *t;
    
16. t=(tree *)malloc(sizeof(tree));
    
17. t->p=NULL;
    
18. t->l=NULL;
    
19. t->r=NULL;
    
20. t->n=1;
    
21. return t;
    
22. }
    
23. void visit (int e)
    
24. { printf("%d ",e);
    
25. }
    
26. 
    
27. void bianli(tree *t,void(*visit)(int)) //函数定义调用函数 需将类型报出，然后用指针*调用
    
28. {
    
29. if(t!=NULL)
    
30. {
    
31. printf("%d ",t->n);
    
32. bianli(t->l,visit);
    
33. bianli(t->r,visit);
    
34. }
    
35. }
    
36. 
    
37. void main()
    
38. {
    
39. tree *t,*a1,*a2,*a3,*a4;
    
40. t=gen();
    
41. a1=(tree *)malloc(sizeof(tree)); //建立根节点的左右孩子
    
42. t->l=a1; //t指向左孩子
    
43. a1->p=t; //a1指向父亲
    
44. a1->n=2;
    
45. a1->l=NULL;
    
46. a1->r=NULL;
    
47. 
    
48. a2=(tree *)malloc(sizeof(tree)); //建立根节点的左右孩子
    
49. t->r=a2; //t指向右孩子
    
50. a2->p=t; //a2指向父亲
    
51. a2->n=3;
    
52. a2->l=NULL;
    
53. a2->r=NULL;
    
54. 
    
55. 
    
56. a3=(tree *)malloc(sizeof(tree)); //建立根节点的左右孩子
    
57. a1->l=a3; //a1指向左孩子
    
58. a3->p=a1; //a3指向父亲
    
59. a3->n=4;
    
60. a3->l=NULL;
    
61. a3->r=NULL;
    
62. 
    
63. a4=(tree *)malloc(sizeof(tree)); //建立根节点的左右孩子
    
64. a1->r=a4; //a1指向右孩子
    
65. a4->p=a1; //a4指向父亲
    
66. a4->n=5;
    
67. a4->l=NULL;
    
68. a4->r=NULL;
    
69. 
    
70. bianli(t,visit);
    
71. 
    
72. 
    
73. }

复制代码

fireofsun

这是递归调用，你可以看成是，它只是输出了自己的值，然后告诉自己的左子树和右子树，你们也用bianli这个方法来处理自己，之后自己就睡觉去了，等到左子树和右子树各自把自己处理完后再返回到这个上层的bianli中。事实上，左子树和右子树也只是输出了自己的值，然后又分别通知自己的左子树和右子树也同样处理，如此分配，只要能保证最低层的处理是正确的而且能返回，那么上层的结果就是建立在正确结果的基础上的，也就一定是正确的。

漠水

fireofsun 发表于 2014-11-8 09:34
这是递归调用，你可以看成是，它只是输出了自己的值，然后告诉自己的左子树和右子树，你们也用bianli这个方 ...

其实我想问的是这里的VISIT函数到底有没有用，经过我刚才的测试，删除了visit函数后程序一样执行。。。
帮我想想是不是多余的。。。。

fireofsun

漠水 发表于 2014-11-8 11:43
其实我想问的是这里的VISIT函数到底有没有用，经过我刚才的测试，删除了visit函数后程序一样执行。。。
...

这里visit的用处就是访问当前节点的内容，这里只是简单的输出数值，但真正开发的时候，节点里不可能就那么点数值，对于节点的访问也可能是很复杂的处理，这就只需要将visit的内容给替换掉就行了。去掉visit程序一样执行，但是如果不访问节点，遍历还有什么意思呢

漠水

fireofsun 发表于 2014-11-8 15:11
这里visit的用处就是访问当前节点的内容，这里只是简单的输出数值，但真正开发的时候，节点里不可能就那 ...

差不多懂了，谢谢