二叉树之链表操作

鬼谷左原

最近学习下了二叉树的基本操作的coding，分享下代码，使用VS编译，下面的程序运行结果：

1. /*
2. *********************************************************************************************************
3. *
4. *    模块名称 : 二叉树
5. *    文件名称 : BiTree.c
6. *    版    本 : V1.0
7. *    说    明 : 使用动态分配的链式结构实现的二叉树和基本操作
8. *   改    进 : 增加对树动态排序；增加destroy tree 的操作；增加求树的深度和各个层数的节点数；每个节点添加父节点，方便求父节点，需要在插入函数里修改一下
9. *    修改记录 :
10. *        版本号  日期        作者     说明
11. *        V1.0    2016-03-27 yao  测试
12. *
13. *    Copyright (C), 2016,SCUTer
14. *
15. *********************************************************************************************************
16. */
17. //                             _ooOoo_  
18. //                            o8888888o  
19. //                            88" . "88  
20. //                            (| -_- |)  
21. //                             O\ = /O  
22. //                         ____/`---'\____  
23. //                       .   ' \\| |// `.  
24. //                        / \\||| : |||// \  
25. //                      / _||||| -:- |||||- \  
26. //                        | | \\\ - /// | |  
27. //                      | \_| ''\---/'' | |  
28. //                       \ .-\__ `-` ___/-. /  
29. //                    ___`. .' /--.--\ `. . __  
30. //                 ."" '< `.___\_<|>_/___.' >'"".  
31. //               | | : `- \`.;`\ _ /`;.`/ - ` : | |  
32. //                  \ \ `-. \_ __\ /__ _/ .-` / /  
33. //          ======`-.____`-.___\_____/___.-`____.-'======  
34. //                             `=---='  
35. //          .............................................  
36. //
37. #include"stdio.h"
38. #include"malloc.h"
39. #define Tree_Type int//定义数的具体类型
40. //定义树结点的结构体
41. typedef struct Tree_Node{
42.     Tree_Type value;
43.     struct Tree_Node *left;
44.     struct Tree_Node *right;
45. }TreeNode_TypeDef;
46. //定义树的结构体，通过结构体操作数
47. typedef struct Bi_tree_Struct{
48.     TreeNode_TypeDef root;
49.     unsigned char(*insert)(Tree_Type, struct Bi_tree_Struct*);
50.     TreeNode_TypeDef*(*find)(Tree_Type, struct Bi_tree_Struct*);
51.     void(*pre_order_traverse)(struct Bi_tree_Struct, void(*callback)(Tree_Type value));
52. }Bi_tree;
53. //-------------------function declare----------------------
54. void init_bitree(Bi_tree*Tree, Tree_Type root_value);
59. void print_tree_node(Tree_Type value)
60. {
61.     printf("%d ",value);
62. }
63. int main(void)
64. {
65.     //树根节点指针
66.      Bi_tree Tree1;
67.      TreeNode_TypeDef*temp;
68.     int i = 0xffffffff;
69.     init_bitree(&Tree1, 1);
70.     Tree1.pre_order_traverse(Tree1, print_tree_node);
71.     printf("\r\n");
72.     Tree1.insert(-1, &Tree1);
73.     if (Tree1.root.left == NULL)
74.     {
75.         if (Tree1.root.right == NULL)
76.             printf("insert error\r\n");
77.     }
78.     Tree1.pre_order_traverse(Tree1, print_tree_node);
79.     printf("\r\n");
80.     printf("insert error code:%d\r\n", Tree1.insert(-1, &Tree1));
81.     Tree1.pre_order_traverse(Tree1, print_tree_node);
82.     printf("\r\n");
83.     Tree1.insert(5, &Tree1);
84.     Tree1.insert(3, &Tree1);
85.     Tree1.insert(2, &Tree1);
86.     Tree1.pre_order_traverse(Tree1, print_tree_node);
87.     temp = Tree1.find(1, &Tree1);
88.     printf("find:%d\r\n", temp->value);
89.     while (i--);
90.     return 0;
91. }
94. //insert
95. //value:要插入的节点数据，
96. //选择插入的树
97. //return:0 sucess;
98. //        1:the data already exist
99. //        2:malloc data unsucess
100. static unsigned char insert(Tree_Type value, Bi_tree*Tree)
101. {
102.     TreeNode_TypeDef*current;
103.     TreeNode_TypeDef*temp;
104.     TreeNode_TypeDef**link;
105.     //从根节点开始
106.     temp = &Tree->root;
107.     link = &temp;
108.     //查找到合适的子树
109.     while ((current = *link) != NULL)
110.     {
111.         //根据大小选择左子树和右子树（确认没有出现重复的值）
112.         if (value < current->value)
113.         {
114.             link = &current->left;
115.         }
116.             
117.         else {
118.             if (value != current->value)
119.                 link = &current->right;
120.             else
121.                 return 1;
122.         }
123.     }
124.     //动态分配内存，插入新的节点
125.     current = malloc(sizeof(TreeNode_TypeDef));
126.     if (current == NULL)
127.         return 2;
128.     else
129.     {
130.         current->value = value;
131.         current->left = NULL;
132.         current->right = NULL;
133.         *link = current;
134.     }
135.     return 0;
136. }
137. //find
138. //value:要查找的节点数据，
139. //选择查找的树
140. //return:NULL don't find the node
141. static TreeNode_TypeDef*find(Tree_Type value, Bi_tree*Tree)
142. {
143.     TreeNode_TypeDef*current;
144.     //从跟节点开始查找
145.     current = &Tree->root;
146.     while (current != NULL && current->value != value)
147.     {
148.     //选择合适的子树
149.         //根据大小选择左子树和右子树（确认没有出现重复的值）
150.         if (value < current->value)
151.             current = current->left;
152.         else {
153.                 current = current->right;
154.         }
155.     }
156.     return current;
157. }
158. //前序遍历，这个函数帮助我们查看所有节点的信息
159. static void do_pre_order_traverse(TreeNode_TypeDef*current, void(*callback)(Tree_Type value))
160. {
161.     if (current != NULL)
162.     {
163.         callback(current->value);
164.         do_pre_order_traverse(current->left, callback);
165.         do_pre_order_traverse(current->right, callback);
166.     }
167. }
168. static void pre_order_traverse(Bi_tree Tree, void(*callback)(Tree_Type value))
169. {
170.     do_pre_order_traverse(&Tree.root, callback);
171. }
172. //初始化二叉树
173. //根节点的值
174. void init_bitree(Bi_tree*Tree, Tree_Type root_value)
175. {
176.     Tree->root.value = root_value;
177.     Tree->root.left = NULL;
178.     Tree->root.right = NULL;
179.     Tree->insert = insert;
180.     Tree->find = find;
181.     Tree->pre_order_traverse = pre_order_traverse;
182. }

复制代码