【遞歸】二叉樹的先序建立及遍歷

數據間隔符為空格，例如:ABC--DE-G--F--- -代表空格

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<conio.h>
5. typedefstruct tree
6. {
7. char ch;
8. struct tree *lchild;
9. struct tree *rchild;
10. }TREE;
12. void createTree(TREE **bt);
13. void fristRoot(TREE **bt);
14. void middleRoot(TREE **bt);
15. void lastRoot(TREE **bt);
16. void destroyTree(TREE **bt);
18. int main()
19. {
20. TREE **bt;
22. printf("Pleas input string:\n");
23. bt = (TREE **)malloc(sizeof(TREE *));
24. createTree(bt);
25. printf("\n先序:\n");
26. fristRoot(bt);
27. printf("\n中序:\n");
28. middleRoot(bt);
29. printf("\n後序:\n");
30. lastRoot(bt);
31. printf("\n");
33. destroyTree(bt);
34. free(bt);
35. return 0;
36. }
38. void createTree(TREE **bt)
39. {
40. char ch;
41. ch = getche();
42. if(ch == ' ')
43. *bt = NULL;
44. else
45. {
46. *bt = (TREE *)malloc(sizeof(TREE));
47. (*bt)->ch = ch;
48. createTree(&((*bt)->lchild));
49. createTree(&((*bt)->rchild));
50. }
51. }
53. void fristRoot(TREE **bt)
54. {
55. if( *bt != NULL)
56. {
57. printf("%c ", (*bt)->ch);
58. fristRoot(&((*bt)->lchild));
59. fristRoot(&((*bt)->rchild));
60. }
61. }
63. void middleRoot(TREE **bt)
64. {
65. if( *bt != NULL)
66. {
67. middleRoot(&((*bt)->lchild));
68. printf("%c ", (*bt)->ch);
69. middleRoot(&((*bt)->rchild));
70. }
71. }
73. void lastRoot(TREE **bt)
74. {
75. if( *bt != NULL)
76. {
77. lastRoot(&((*bt)->lchild));
78. lastRoot(&((*bt)->rchild));
79. printf("%c ", (*bt)->ch);
80. }
81. }
83. void destroyTree(TREE **bt)
84. {
85. if( *bt != NULL)
86. {
87. destroyTree( &((*bt)->lchild) );
88. destroyTree( &((*bt)->rchild) );
89. free(*bt);
90. }
91. }