二叉树结点
首先定义一个二叉树结点的结构体
1. typedef struct MyTreeNode 2. { 3. struct MyTreeNode* left; 4. struct MyTreeNode* right; 5. char data; 6. }MyTreeNode;
创建一棵二叉树
使用#号法创建一棵二叉树，如果没有左/右子树，则用#号代替，采取先创建根结点、然后创建左子树，最后创建右子树的方法创建二叉树（前序遍历），代码如下：
1. MyTreeNode * create_tree() 2. { 3. MyTreeNode* node = NULL; 4. char c; 5. scanf("%c", &c); 6. if (c == '#') 7. { 8. node = NULL; 9. } 10. else 11. { 12. node = (MyTreeNode*)malloc(sizeof(MyTreeNode)); 13. node->data = c; 14. node->left = create_tree(); 15. node->right = create_tree(); 16. } 17. return node; 18. }
释放一棵二叉树
因为二叉树在创建的时候，所有结点都是malloc分配的，所以需要我们通过free来实现释放二叉树的内存。在释放二叉树的内存时，一定要先释放左右子树，最后释放根结点。代码如下：
1. void free_tree(MyTreeNode* tree) 2. { 3. if (tree != NULL) 4. { 5. if (tree->left != NULL) 6. { 7. free_tree(tree->left); 8. tree->left = NULL; 9. } 10. if (tree->right != NULL) 11. { 12. free_tree(tree->right); 13. tree->right = NULL; 14. } 15. free(tree); 16. tree = NULL; 17. } 18. }
算法测试
首先创建一棵二叉树如下图所示，使用本文的算法创建，并使用前序遍历打印
测试程序
1. #define _CRT_SECURE_NO_WARNINGS 2. #include <stdlib.h> 3. #include <string.h> 4. #include <stdio.h> 5. 6. //树结点结构体 7. typedef struct MyTreeNode 8. { 9. struct MyTreeNode* left; 10. struct MyTreeNode* right; 11. char data; 12. }MyTreeNode; 13. 14. //二叉树的前序遍历 15. void preorder_traversal(MyTreeNode* tree) 16. { 17. if (tree == NULL) 18. { 19. return; 20. } 21. printf("%c ", tree->data); 22. preorder_traversal(tree->left); 23. preorder_traversal(tree->right); 24. } 25. 26. //创建一颗二叉树（先创建根，后创建左子树，再创建右子树） 27. MyTreeNode * create_tree() 28. { 29. MyTreeNode* node = NULL; 30. char c; 31. scanf("%c", &c); 32. if (c == '#') 33. { 34. node = NULL; 35. } 36. else 37. { 38. node = (MyTreeNode*)malloc(sizeof(MyTreeNode)); 39. node->data = c; 40. node->left = create_tree(); 41. node->right = create_tree(); 42. } 43. return node; 44. } 45. 46. //释放一颗二叉树（先释放左右子树，后释放根） 47. void free_tree(MyTreeNode* tree) 48. { 49. if (tree != NULL) 50. { 51. if (tree->left != NULL) 52. { 53. free_tree(tree->left); 54. tree->left = NULL; 55. } 56. if (tree->right != NULL) 57. { 58. free_tree(tree->right); 59. tree->right = NULL; 60. } 61. free(tree); 62. tree = NULL; 63. } 64. } 65. 66. int main() 67. { 68. MyTreeNode* tree = create_tree(); 69. 70. printf("前序遍历："); 71. preorder_traversal(tree); 72. printf("\n"); 73. 74. free_tree(tree); 75. 76. system("pause"); 77. return 0; 78. }
运行并输入
ABC#D###EF##G##
