devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

【数据结构】（C语言）：二叉搜索树

作者：秋刀鱼在做梦 | 2024-07-01 18:01:54

赞

踩

【数据结构】（C语言）：二叉搜索树

二叉搜索树：

  • 树不是线性的，是层级结构。
  • 基本单位是节点，每个节点最多2个子节点。
  • 有序。每个节点，其左子节点都比它小，其右子节点都比它大。
  • 每个子树都是一个二叉搜索树。每个节点及其所有子节点形成子树。
  • 可以是空树。

添加元素：从根节点开始，比对数值。若比它小，往左子树比对；若比它大，往右子树比对；直到找到为空，则为新元素的位置。

删除元素：

  1. 若删除的节点为叶子节点（即无子节点），则直接删除。
  2. 若删除的节点只有左子节点，则左子节点替代删除节点。
  3. 若删除的节点只有右子节点，则右子节点替代删除节点。
  4. 若删除的节点既有左子节点又有右子节点，则找到直接前驱（即删除节点的左子树中的最大值，即删除节点的左子节点的最右节点），直接前驱的值替代删除节点的值，删除直接前驱节点。

清空树：从根节点开始遍历，依次从叶子节点开始 释放每个节点的内存空间，最终根节点指向NULL。

遍历元素：（可使用递归）

  • 前序遍历（顺序：根节点、左子节点、右子节点）。
  • 中序遍历（顺序：左子节点、根节点、右子节点）。
  • 后序遍历（顺序：左子节点、右子节点、根节点）。

查找元素：从根节点开始，比对数值。若比它小，往左子树查找；若比它大，往右子树查找；直到找到该元素，则返回1（true），若没有，则返回0（false）。

C语言实现：（使用链表实现）

 创建结构体数据类型（记录二叉搜索树的根节点和数据个数）：

  1. typedef struct Link
  2. {
  3. 	LinkNode *root;			// 根节点
  4. 	int length;			    // 统计有多少数据
  5. } LinkBST;                  // 别名

创建二叉搜索树，并初始化：

  1. LinkBST bst;
  2. bst.root = NULL;    // 根节点，初始化为NULL
  3. bst.length = 0;     // 数据个数，初始化为0

创建节点（结构体数据类型），并创建具体节点实例的函数：

  1. // 节点（结构体数据类型）
  2. typedef struct Node
  3. {
  4. 	int value;			    // 数据类型为整型
  5. 	struct Node *left;		// 左子节点
  6. 	struct Node *right;		// 右子节点
  7. }LinkNode;                  // 别名
  1. // 函数：创建节点
  2. LinkNode *createNode(int data)
  3. {
  4. 	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));    // 分配节点内存空间
  5.  
  6. 	if(node == NULL)
  7. 	{
  8. 		perror("Memory allocation failed");
  9. 		exit(-1);
  10. 	}
  11. 	node->value = data;    // 数据
  12. 	node->left = NULL;     // 左子节点，初始化为NULL
  13. 	node->right = NULL;    // 右子节点，初始化为NULL
  14. 	return node;
  15. }

添加元素：

  1. void add(LinkBST *bst, int data)	// add element
  2. {
  3. 	// 函数：往二叉搜索树中添加元素	
  4. 	LinkNode *addNode(LinkNode *node, int data)
  5. 	{
  6. 		if(node == NULL)
  7. 		{
  8. 			LinkNode *newnode = createNode(data);
  9. 			node = newnode;
  10. 			bst->length++;    // 每添加一个元素，length+1
  11. 			return node;
  12. 		}
  13. 		if(data < node->value) node->left = addNode(node->left, data);
  14. 		else if(data > node->value) node->right = addNode(node->right, data);
  15. 		return node;
  16. 	}
  17.  
  18. 	// 从根节点开始比对，root指针始终指向二叉搜索树的根节点
  19. 	bst->root = addNode(bst->root, data);	
  20. }

删除元素：

  1. void delete(LinkBST *bst, int data)	// delete element
  2. {
  3. 	// 函数：删除节点	
  4. 	LinkNode *del(LinkNode *node)
  5. 	{   
  6.         // 若只有右子节点，则右子节点替代删除节点
  7. 		if(node->left == NULL)
  8. 		{
  9. 			bst->length--;        // 每删除一个元素，length-1
  10. 			return node->right;
  11. 		}
  12.         // 若只有左子节点，则左子节点替代删除节点
  13. 		else if(node->right == NULL)
  14. 		{
  15. 			bst->length--;        // 每删除一个元素，length-1
  16. 			return node->left;
  17. 		}
  18.         // 左右子节点都有，则直接前驱(左子节点的最右节点)替代删除节点，并删除直接前驱
  19. 		else if(node->left && node->right)
  20. 		{
  21. 			LinkNode *tmp = node, *cur = node->left;
  22. 			while(cur->right)
  23. 			{
  24. 				tmp = cur;
  25. 				cur = cur->right;
  26. 			}
  27. 			node->value = cur->value;
  28. 			if(tmp != node) tmp->right = cur->left;
  29. 			else tmp->left = cur->left;
  30. 			bst->length--;        // 每删除一个元素，length-1
  31. 			return node;
  32. 		}
  33. 	}
  34.  
  35. 	// 函数：找到将要删除的节点
  36. 	LinkNode *delNode(LinkNode *node, int data)
  37. 	{
  38. 		if(node == NULL) return node;
  39. 		if(data == node->value) node = del(node);
  40. 		else if(data < node->value) node->left = delNode(node->left, data);
  41. 		else if(data > node->value) node->right = delNode(node->right, data);
  42. 		return node;
  43. 	}	
  44. 	
  45. 	// 从根节点开始比对。root指针始终指向二叉搜索树的根节点
  46. 	bst->root = delNode(bst->root, data);	
  47. }

清空树：

  1. void clear(LinkBST *bst)
  2. {
  3. 	// 函数：释放每个节点的内存空间
  4. 	void clearNode(LinkNode *node)
  5. 	{
  6. 		if(node->left == NULL && node->right == NULL)
  7. 		{
  8. 			free(node);        // 使用malloc动态分配内存空间，不使用时需使用free释放内存空间
  9. 			node == NULL;      // 释放内存空间后，指针指向NULL，避免野指针
  10. 			return ;
  11. 		}
  12. 		if(node->left) clearNode(node->left);
  13. 		if(node->right) clearNode(node->right);
  14. 	}
  15. 	
  16. 	// 树非空，释放所有节点的内存空间，根节点为NULL，数据个数为0
  17. 	if(bst->root == NULL) return ;
  18. 	clearNode(bst->root);    // 从根节点开始遍历，依次从叶子节点开始释放内存空间
  19. 	bst->root = NULL;        // 根节点指向NULL
  20. 	bst->length = 0;         // 数据个数为0
  21. }

遍历元素：（使用递归）

  1. // 前序遍历（根，左，右）
  2. void pretravel(LinkNode *node)
  3. {
  4. 	if(node == NULL) return ;
  5. 	printf("%d  ", node->value);
  6. 	pretravel(node->left);
  7. 	pretravel(node->right);
  8. }
  1. // 中序遍历（左，根，右）
  2. void midtravel(LinkNode *node)
  3. {
  4. 	if(node == NULL) return ;
  5. 	midtravel(node->left);
  6. 	printf("%d  ", node->value);
  7. 	midtravel(node->right);
  8. }
  1. // 后序遍历（左，右，根）
  2. void posttravel(LinkNode *node)
  3. {
  4. 	if(node == NULL) return ;
  5. 	posttravel(node->left);
  6. 	posttravel(node->right);
  7. 	printf("%d  ", node->value);
  8. }

查找元素：

找到元素，返回1(true)；没找到，返回0(false)。

  1. int find(LinkNode *node, int data)
  2. {
  3. 	if(node ==  NULL) return 0;
  4. 	if(data == node->value) return 1;
  5. 	if(data < node->value) find(node->left, data);
  6. 	else if(data > node->value) find(node->right, data);	
  7. }

完整代码：（bst.c）

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <stdbool.h>
  4.  
  5. /* structure */
  6. typedef struct Node			// linkedlist node
  7. {
  8. 	int value;			    // value type is integer
  9. 	struct Node *left;		// left child node
  10. 	struct Node *right;		// right child node
  11. }LinkNode;
  12.  
  13. typedef struct Link			// binary search tree
  14. {
  15. 	LinkNode *root;			// root node of the tree
  16. 	int length;			    // the number of the tree
  17. } LinkBST;
  18.  
  19. /* function prototype */
  20. void add(LinkBST *, int);		// add element to the tree
  21. void delete(LinkBST *, int);	// delete element from the tree
  22. void clear(LinkBST *);			// clear the tree
  23. void pretravel(LinkNode *);		// show element one by one,(root,left,right)
  24. void midtravel(LinkNode *);		// show element one by one,(left,root,right)
  25. void posttravel(LinkNode *);	// show element one by one,(left,right,root)
  26. int find(LinkNode *, int);		// if find data,return 1(true),or return 0(false)
  27.  
  28. /* main function */
  29. int main(void)
  30. {
  31. 	// create binary search tree and initialization
  32. 	LinkBST bst;
  33. 	bst.root = NULL;
  34. 	bst.length = 0;
  35. 	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
  36. 	
  37. 	add(&bst, 15);
  38. 	add(&bst, 8);
  39. 	add(&bst, 23);
  40. 	add(&bst, 10);
  41. 	add(&bst, 12);
  42. 	add(&bst, 19);
  43. 	add(&bst, 6);
  44. 	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
  45.  
  46. 	printf("midtravel: ");
  47. 	midtravel(bst.root);
  48. 	printf("\n");
  49. 	printf("pretravel: ");
  50. 	pretravel(bst.root);
  51. 	printf("\n");
  52. 	printf("posttravel: ");
  53. 	posttravel(bst.root);
  54. 	printf("\n");
  55. 	
  56. 	printf("find 10 (1:true, 0:false): %d\n", find(bst.root, 10));
  57. 	printf("find 9 (1:true, 0:false): %d\n", find(bst.root, 9));
  58. 	
  59. 	delete(&bst, 23);
  60. 	delete(&bst, 15);
  61. 	delete(&bst, 6);
  62.  
  63. 	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
  64. 	printf("midtravel: ");
  65. 	midtravel(bst.root);
  66. 	printf("\n");
  67. 	printf("pretravel: ");
  68. 	pretravel(bst.root);
  69. 	printf("\n");
  70. 	printf("posttravel: ");
  71. 	posttravel(bst.root);
  72. 	printf("\n");
  73.  
  74. 	clear(&bst);
  75. 	printf("isempty(1:true, 0:false): %d, length is %d\n",  bst.root==NULL, bst.length);
  76. 	return 0;
  77. }
  78.  
  79. /* subfunction */
  80. LinkNode *createNode(int data)		// create a node
  81. {
  82. 	LinkNode *node = (LinkNode *)malloc(sizeof(LinkNode));
  83.  
  84. 	if(node == NULL)
  85. 	{
  86. 		perror("Memory allocation failed");
  87. 		exit(-1);
  88. 	}
  89. 	node->value = data;
  90. 	node->left = NULL;
  91. 	node->right = NULL;
  92. 	return node;
  93. }
  94.  
  95. void add(LinkBST *bst, int data)	// add element
  96. {
  97. 	// subfunction(recursion): add element to the binary search tree	
  98. 	LinkNode *addNode(LinkNode *node, int data)
  99. 	{
  100. 		if(node == NULL)
  101. 		{
  102. 			LinkNode *newnode = createNode(data);
  103. 			node = newnode;
  104. 			bst->length++;
  105. 			return node;
  106. 		}
  107. 		if(data < node->value) node->left = addNode(node->left, data);
  108. 		else if(data > node->value) node->right = addNode(node->right, data);
  109. 		return node;
  110. 	}
  111.  
  112. 	// root node receive the result
  113. 	bst->root = addNode(bst->root, data);	
  114. }
  115.  
  116. void delete(LinkBST *bst, int data)	// delete element
  117. {
  118. 	// subfunction(recursion): delete element from the binary search tree	
  119. 	LinkNode *del(LinkNode *node)
  120. 	{
  121. 		if(node->left == NULL)
  122. 		{
  123. 			bst->length--;
  124. 			return node->right;
  125. 		}
  126. 		else if(node->right == NULL)
  127. 		{
  128. 			bst->length--;
  129. 			return node->left;
  130. 		}
  131. 		else if(node->left && node->right)
  132. 		{
  133. 			LinkNode *tmp = node, *cur = node->left;
  134. 			while(cur->right)
  135. 			{
  136. 				tmp = cur;
  137. 				cur = cur->right;
  138. 			}
  139. 			node->value = cur->value;
  140. 			if(tmp != node) tmp->right = cur->left;
  141. 			else tmp->left = cur->left;
  142. 			bst->length--;
  143. 			return node;
  144. 		}
  145. 	}
  146.  
  147. 	// subfunction: find delete node,return node
  148. 	LinkNode *delNode(LinkNode *node, int data)
  149. 	{
  150. 		if(node == NULL) return node;
  151. 		if(data == node->value) node = del(node);
  152. 		else if(data < node->value) node->left = delNode(node->left, data);
  153. 		else if(data > node->value) node->right = delNode(node->right, data);
  154. 		return node;
  155. 	}	
  156. 	
  157. 	// root node receive the result
  158. 	bst->root = delNode(bst->root, data);	
  159. }
  160.  
  161. void clear(LinkBST *bst)		// clear the tree
  162. {
  163. 	// function: free memory space on ecah node
  164. 	void clearNode(LinkNode *node)
  165. 	{
  166. 		if(node->left == NULL && node->right == NULL)
  167. 		{
  168. 			free(node);
  169. 			node == NULL;
  170. 			return ;
  171. 		}
  172. 		if(node->left) clearNode(node->left);
  173. 		if(node->right) clearNode(node->right);
  174. 	}
  175. 	
  176. 	// if not empty tree,free memory space on each node,root is NULL and length is 0
  177. 	if(bst->root == NULL) return ;
  178. 	clearNode(bst->root);
  179. 	bst->root = NULL;
  180. 	bst->length = 0;
  181. }
  182.  
  183. void pretravel(LinkNode *node)		// show element one by one,(root,left,right)
  184. {
  185. 	if(node == NULL) return ;
  186. 	printf("%d  ", node->value);
  187. 	pretravel(node->left);
  188. 	pretravel(node->right);
  189. }
  190.  
  191. void midtravel(LinkNode *node)		// show element one by one,(left,root,right)
  192. {
  193. 	if(node == NULL) return ;
  194. 	midtravel(node->left);
  195. 	printf("%d  ", node->value);
  196. 	midtravel(node->right);
  197. }
  198.  
  199. void posttravel(LinkNode *node)		// show element one by one,(left,right,root)
  200. {
  201. 	if(node == NULL) return ;
  202. 	posttravel(node->left);
  203. 	posttravel(node->right);
  204. 	printf("%d  ", node->value);
  205. }
  206.  
  207. int find(LinkNode *node, int data)	// if find data,return 1(true),or return 0(false)
  208. {
  209. 	if(node ==  NULL) return 0;
  210. 	if(data == node->value) return 1;
  211. 	if(data < node->value) find(node->left, data);
  212. 	else if(data > node->value) find(node->right, data);	
  213. }

编译链接： gcc -o bst bst.c

执行可执行文件： ./bst

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/777214
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号