devbox
神奇cpp
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

二叉树--兄弟孩子表示法_二叉树实现孩子兄弟表示法

作者：神奇cpp | 2024-08-22 02:05:54

赞

踩

二叉树实现孩子兄弟表示法

  1. //BTree.h
  2.  
  3. #ifndef _BTREE_H_
  4. #define _BTREE_H_
  5.  
  6. #define BT_LEFT 0
  7. #define BT_RIGHT 1
  8.  
  9. typedef void BTree;
  10. typedef unsigned long long BTPos;
  11.  
  12. typedef struct _tag_BTreeNode BTreeNode;
  13. struct _tag_BTreeNode
  14. {
  15.     BTreeNode* left;
  16.     BTreeNode* right;
  17. };
  18.  
  19. typedef void (BTree_Printf)(BTreeNode*);
  20.  
  21. BTree* BTree_Create();
  22.  
  23. void BTree_Destroy(BTree* tree);
  24.  
  25. void BTree_Clear(BTree* tree);
  26.  
  27. int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);
  28.  
  29. BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);
  30.  
  31. BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);
  32.  
  33. BTreeNode* BTree_Root(BTree* tree);
  34.  
  35. int BTree_Height(BTree* tree);
  36.  
  37. int BTree_Count(BTree* tree);
  38.  
  39. int BTree_Degree(BTree* tree);
  40.  
  41. void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);
  42.  
  43. #endif

  1. //BTree.c
  2. #include <stdio.h>
  3. #include <malloc.h>
  4. #include "BTree.h"
  5.  
  6. typedef struct _tag_BTree TBTree;
  7. struct _tag_BTree
  8. {
  9.     int count;
  10.     BTreeNode* root;
  11. };
  12.  
  13. static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) // O(n)
  14. {
  15.     int i = 0;
  16.     
  17.     if( (node != NULL) && (pFunc != NULL) )
  18.     {
  19.         for(i=0; i<format; i++)
  20.         {
  21.             printf("%c", div);
  22.         }
  23.         
  24.         pFunc(node);
  25.         
  26.         printf("\n");
  27.         
  28.         if( (node->left != NULL) || (node->right != NULL) )
  29.         {
  30.             recursive_display(node->left, pFunc, format + gap, gap, div);
  31.             recursive_display(node->right, pFunc, format + gap, gap, div);
  32.         }
  33.     }
  34.     else
  35.     {
  36.         for(i=0; i<format; i++)
  37.         {
  38.             printf("%c", div);
  39.         }
  40.         printf("\n");
  41.     }
  42. }
  43.  
  44. static int recursive_count(BTreeNode* root) // O(n)
  45. {
  46.     int ret = 0;
  47.     
  48.     if( root != NULL )
  49.     {
  50.         ret = recursive_count(root->left) + 1 + recursive_count(root->right);
  51.     }
  52.     
  53.     return ret;
  54. }
  55.  
  56. static int recursive_height(BTreeNode* root) // O(n)
  57. {
  58.     int ret = 0;
  59.     
  60.     if( root != NULL )
  61.     {
  62.         int lh = recursive_height(root->left);
  63.         int rh = recursive_height(root->right);
  64.         
  65.         ret = ((lh > rh) ? lh : rh) + 1;
  66.     }
  67.     
  68.     return ret;
  69. }
  70.  
  71. static int recursive_degree(BTreeNode* root) // O(n)
  72. {
  73.     int ret = 0;
  74.     
  75.     if( root != NULL )
  76.     {
  77.         if( root->left != NULL )
  78.         {
  79.             ret++;
  80.         }
  81.         
  82.         if( root->right != NULL )
  83.         {
  84.             ret++;
  85.         }
  86.         
  87.         if( ret == 1 )
  88.         {
  89.             int ld = recursive_degree(root->left);
  90.             int rd = recursive_degree(root->right);
  91.             
  92.             if( ret < ld )
  93.             {
  94.                 ret = ld;
  95.             }
  96.             
  97.             if( ret < rd )
  98.             {
  99.                 ret = rd;
  100.             }
  101.         }
  102.     }
  103.     
  104.     return ret;
  105. }
  106.  
  107. BTree* BTree_Create() // O(1)
  108. {
  109.     TBTree* ret = (TBTree*)malloc(sizeof(TBTree));
  110.     
  111.     if( ret != NULL )
  112.     {
  113.         ret->count = 0;
  114.         ret->root = NULL;
  115.     }
  116.     
  117.     return ret;
  118. }
  119.  
  120. void BTree_Destroy(BTree* tree) // O(1)
  121. {
  122.     free(tree);
  123. }
  124.  
  125. void BTree_Clear(BTree* tree) // O(1)
  126. {
  127.     TBTree* btree = (TBTree*)tree;
  128.     
  129.     if( btree != NULL )
  130.     {
  131.         btree->count = 0;
  132.         btree->root = NULL;
  133.     }
  134. }
  135.  
  136. int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) // O(n) 
  137. {
  138.     TBTree* btree = (TBTree*)tree;
  139.     int ret = (btree != NULL) && (node != NULL) && ((flag == BT_LEFT) || (flag == BT_RIGHT));
  140.     int bit = 0;
  141.     
  142.     if( ret )
  143.     {
  144.         BTreeNode* parent = NULL;
  145.         BTreeNode* current = btree->root;
  146.         
  147.         node->left = NULL;
  148.         node->right = NULL;
  149.         
  150.         while( (count > 0) && (current != NULL) )
  151.         {
  152.             bit = pos & 1;
  153.             pos = pos >> 1;
  154.             
  155.             parent = current;
  156.             
  157.             if( bit == BT_LEFT )
  158.             {
  159.                 current = current->left;
  160.             }
  161.             else if( bit == BT_RIGHT )
  162.             {
  163.                 current = current->right;
  164.             }
  165.             
  166.             count--;
  167.         }
  168.         
  169.         if( flag == BT_LEFT )
  170.         {
  171.             node->left = current;
  172.         }
  173.         else if( flag == BT_RIGHT )
  174.         {
  175.             node->right = current;
  176.         }
  177.         
  178.         if( parent != NULL )
  179.         {
  180.             if( bit == BT_LEFT )
  181.             {
  182.                 parent->left = node;
  183.             }
  184.             else if( bit == BT_RIGHT )
  185.             {
  186.                 parent->right = node;
  187.             }
  188.         }
  189.         else
  190.         {
  191.             btree->root = node;
  192.         }
  193.         
  194.         btree->count++;
  195.     }
  196.     
  197.     return ret;
  198. }
  199.  
  200. BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) // O(n)
  201. {
  202.     TBTree* btree = (TBTree*)tree;
  203.     BTreeNode* ret = NULL; 
  204.     int bit = 0;
  205.     
  206.     if( btree != NULL )
  207.     {
  208.         BTreeNode* parent = NULL;
  209.         BTreeNode* current = btree->root;
  210.         
  211.         while( (count > 0) && (current != NULL) )
  212.         {
  213.             bit = pos & 1;
  214.             pos = pos >> 1;
  215.             
  216.             parent = current;
  217.             
  218.             if( bit == BT_LEFT )
  219.             {
  220.                 current = current->left;
  221.             }
  222.             else if( bit == BT_RIGHT )
  223.             {
  224.                 current = current->right;
  225.             }
  226.             
  227.             count--;
  228.         }
  229.         
  230.         if( parent != NULL )
  231.         {
  232.             if( bit == BT_LEFT )
  233.             {
  234.                 parent->left = NULL;
  235.             }
  236.             else if( bit == BT_RIGHT )
  237.             {
  238.                 parent->right = NULL;
  239.             }
  240.         }
  241.         else
  242.         {
  243.             btree->root = NULL;
  244.         }
  245.         
  246.         ret = current;
  247.         
  248.         btree->count = btree->count - recursive_count(ret);
  249.     }
  250.     
  251.     return ret;
  252. }
  253.  
  254. BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) // O(n)
  255. {
  256.     TBTree* btree = (TBTree*)tree;
  257.     BTreeNode* ret = NULL; 
  258.     int bit = 0;
  259.     
  260.     if( btree != NULL )
  261.     {
  262.         BTreeNode* current = btree->root;
  263.         
  264.         while( (count > 0) && (current != NULL) )
  265.         {
  266.             bit = pos & 1;
  267.             pos = pos >> 1;
  268.             
  269.             if( bit == BT_LEFT )
  270.             {
  271.                 current = current->left;
  272.             }
  273.             else if( bit == BT_RIGHT )
  274.             {
  275.                 current = current->right;
  276.             }
  277.             
  278.             count--;
  279.         }
  280.         
  281.         ret = current;
  282.     }
  283.     
  284.     return ret;
  285. }
  286.  
  287. BTreeNode* BTree_Root(BTree* tree) // O(1)
  288. {
  289.     TBTree* btree = (TBTree*)tree;
  290.     BTreeNode* ret = NULL;
  291.     
  292.     if( btree != NULL )
  293.     {
  294.         ret = btree->root;
  295.     }
  296.     
  297.     return ret;
  298. }
  299.  
  300. int BTree_Height(BTree* tree) // O(n)
  301. {
  302.     TBTree* btree = (TBTree*)tree;
  303.     int ret = 0;
  304.     
  305.     if( btree != NULL )
  306.     {
  307.         ret = recursive_height(btree->root);
  308.     }
  309.     
  310.     return ret;
  311. }
  312.  
  313. int BTree_Count(BTree* tree) // O(1)
  314. {
  315.     TBTree* btree = (TBTree*)tree;
  316.     int ret = 0;
  317.     
  318.     if( btree != NULL )
  319.     {
  320.         ret = btree->count;
  321.     }
  322.     
  323.     return ret;
  324. }
  325.  
  326. int BTree_Degree(BTree* tree) // O(n)
  327. {
  328.     TBTree* btree = (TBTree*)tree;
  329.     int ret = 0;
  330.     
  331.     if( btree != NULL )
  332.     {
  333.         ret = recursive_degree(btree->root);
  334.     }
  335.     
  336.     return ret;
  337. }
  338.  
  339. void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) // O(n)
  340. {
  341.     TBTree* btree = (TBTree*)tree;
  342.     
  343.     if( btree != NULL )
  344.     {
  345.         recursive_display(btree->root, pFunc, 0, gap, div);
  346.     }
  347. }

  1. //main.c
  2.  
  3. #include <stdio.h>
  4. #include <stdlib.h>
  5. #include "BTree.h"
  6.  
  7. /* run this program using the console pauser or add your own getch, system("pause") or input loop */
  8.  
  9. struct Node
  10. {
  11.     BTreeNode header;
  12.     char v;
  13. };
  14.  
  15. void printf_data(BTreeNode* node)
  16. {
  17.     if( node != NULL )
  18.     {
  19.         printf("%c", ((struct Node*)node)->v);
  20.     }
  21. }
  22.  
  23. int main(int argc, char *argv[])
  24. {
  25.     BTree* tree = BTree_Create();
  26.     
  27.     struct Node n1 = {{NULL, NULL}, 'A'};
  28.     struct Node n2 = {{NULL, NULL}, 'B'};
  29.     struct Node n3 = {{NULL, NULL}, 'C'};
  30.     struct Node n4 = {{NULL, NULL}, 'D'};
  31.     struct Node n5 = {{NULL, NULL}, 'E'};
  32.     struct Node n6 = {{NULL, NULL}, 'F'};
  33.     
  34.     BTree_Insert(tree, (BTreeNode*)&n1, 0, 0, 0);
  35.     BTree_Insert(tree, (BTreeNode*)&n2, 0x00, 1, 0);
  36.     BTree_Insert(tree, (BTreeNode*)&n3, 0x01, 1, 0);
  37.     BTree_Insert(tree, (BTreeNode*)&n4, 0x00, 2, 0);
  38.     BTree_Insert(tree, (BTreeNode*)&n5, 0x02, 2, 0);
  39.     BTree_Insert(tree, (BTreeNode*)&n6, 0x02, 3, 0);
  40.     
  41.     printf("Height: %d\n", BTree_Height(tree));
  42.     printf("Degree: %d\n", BTree_Degree(tree));
  43.     printf("Count: %d\n", BTree_Count(tree));
  44.     printf("Position At (0x02, 2): %c\n", ((struct Node*)BTree_Get(tree, 0x02, 2))->v);
  45.     printf("Full Tree: \n");
  46.     
  47.     BTree_Display(tree, printf_data, 4, '-');
  48.     
  49.     BTree_Delete(tree, 0x00, 1);
  50.     
  51.     printf("After Delete B: \n");
  52.     printf("Height: %d\n", BTree_Height(tree));
  53.     printf("Degree: %d\n", BTree_Degree(tree));
  54.     printf("Count: %d\n", BTree_Count(tree));
  55.     printf("Full Tree: \n");
  56.     
  57.     BTree_Display(tree, printf_data, 4, '-');
  58.     
  59.     BTree_Clear(tree);
  60.     
  61.     printf("After Clear: \n");
  62.     printf("Height: %d\n", BTree_Height(tree));
  63.     printf("Degree: %d\n", BTree_Degree(tree));
  64.     printf("Count: %d\n", BTree_Count(tree));
  65.     
  66.     BTree_Display(tree, printf_data, 4, '-');
  67.     
  68.     BTree_Destroy(tree);
  69.     
  70. 	return 0;
  71. }

  1. //my design --BTree.c
  2.  
  3. #include "BTree.h"
  4. #include <malloc.h>
  5. #include <stdio.h>
  6.  
  7.  
  8. typedef struct _tag_TBTree TBTree;
  9. struct _tag_TBTree     //define the node of header 
  10. {
  11. 	int count;
  12. 	BTreeNode* root;
  13. };
  14.  
  15. static int recursive_degree(BTreeNode* root)
  16. {
  17. 	int ret = 0;
  18. 	if(root!=NULL)
  19. 	{
  20. 		if(root->left!=NULL)
  21. 		{
  22. 			ret++;	
  23. 		}	
  24. 		if(root->right!=NULL)
  25. 		{
  26. 			ret++;	
  27. 		}
  28. 		if(ret == 1)
  29. 		{
  30. 			int ld = recursive_degree(root->left);
  31. 			int rd = recursive_degree(root->right);	
  32. 			
  33. 			if(ret < ld)
  34. 			{
  35. 				ret = ld;	
  36. 			}
  37. 			if(ret < rd)
  38. 			{
  39. 				ret = rd;	
  40. 			}
  41. 		}
  42. 	}
  43. 	return ret;
  44. }
  45. static int recursive_height(BTreeNode* root)
  46. {
  47. 	int ret = 0;
  48. 	if(root!=NULL)
  49. 	{
  50. 		int lh = recursive_height(root->left);
  51. 		int rh = recursive_height(root->right);	
  52. 		ret = ((lh>rh)?lh:rh) + 1;
  53. 	}
  54. 	return ret;
  55. }
  56. static int recursive_count(BTreeNode* node)
  57. {
  58. 	int ret = 0;
  59. 	
  60. 	if(node!=NULL)
  61. 	{
  62. 		ret = recursive_count(node->left) + 1 + recursive_count(node->right);	
  63. 	}
  64. 	return ret;
  65. }
  66. static void recursive_display(BTreeNode* node,BTree_Printf* pFunc,int format,int gap,char div)
  67. {
  68. 	int i = 0;
  69. 	if((node!=NULL)&&(pFunc!=NULL))
  70. 	{
  71. 		for(i=0;i<format;i++)
  72. 		{
  73. 			printf("%c",div);	
  74. 		}
  75. 		pFunc(node);
  76. 		printf("\n");
  77. 		if((node->left!=NULL)||(node->right!=NULL))
  78. 		{
  79. 			recursive_display(node->left,pFunc,format+gap,gap,div);
  80. 			recursive_display(node->right,pFunc,format+gap,gap,div);	
  81. 		}	
  82. 	}
  83. 	else   //when there  has only-left child node or only-right child node,print the char to fill the place
  84. 	{
  85. 		for(i=0;i<format;i++)
  86. 		{
  87. 			printf("%c",div);	
  88. 		}
  89. 		printf("\n");	
  90. 	}	
  91. }
  92.  
  93. BTree* BTree_Create()
  94. {
  95. 	TBTree* ret = (TBTree*)malloc(sizeof(TBTree));
  96. 	if(ret != NULL)
  97. 	{
  98. 		ret->count = 0;
  99. 		ret->root = NULL;	
  100. 	}
  101. 	return ret;
  102. }
  103. void BTree_Destroy(BTree* tree)
  104. {
  105. 	free(tree);
  106. }
  107.  
  108. void BTree_Clear(BTree* tree)
  109. {
  110. 	TBTree* btree = (TBTree*)tree;
  111. 	if(btree != NULL)
  112. 	{
  113. 		btree->count = 0;
  114. 		btree->root = NULL;	
  115. 	}
  116. }
  117.  
  118. int BTree_Insert(BTree* tree,BTreeNode* node,BTPos pos,int count,int flag)   // pos :position; count :moving times;
  119. {
  120. 	int ret = 0;
  121. 	int bit = 0;
  122. 	TBTree* btree = (TBTree*)tree;
  123. 	ret = (btree!=NULL)&&(node!=NULL)&&((flag==BT_LEFT)||(flag==BT_RIGHT));
  124. 	if(ret)
  125. 	{
  126. 		BTreeNode* parent = NULL;
  127. 		BTreeNode* current = btree->root;		
  128. 		
  129. 		node->left = NULL;
  130. 		node->right = NULL;
  131. 		
  132. 		while((count>0)&&(current!=NULL))
  133. 		{
  134. 			bit = pos & 1;
  135. 			pos = pos >> 1;
  136. 			
  137. 			parent = current;
  138. 			
  139. 			if(bit==BT_LEFT)
  140. 			{
  141. 				current = current->left;	
  142. 			}
  143. 			else if(bit==BT_RIGHT)
  144. 			{
  145. 				current = current->right;	
  146. 			}
  147. 			count--;
  148. 			
  149. 		}
  150. 		if(flag==BT_LEFT)    //when the current node has some children node,the current node should be inserted after the node
  151. 		{
  152. 			node->left = current;	
  153. 		}
  154. 		else if(flag == BT_RIGHT)
  155. 		{
  156. 			node->right = current;	
  157. 		}	
  158. 		
  159. 		if(parent!=NULL)
  160. 		{
  161. 			if(bit == BT_LEFT)
  162. 			{
  163. 				parent->left = node;		
  164. 			}	
  165. 			else if(bit == BT_RIGHT)
  166. 			{
  167. 				parent->right = node;
  168. 			}
  169. 		}
  170. 		else      //insert the first node
  171. 		{
  172. 			btree->root = node;	
  173. 		}
  174. 		btree->count++;
  175. 	}
  176.  
  177. 	return ret;
  178. } 
  179.  
  180. void BTree_Display(BTree* tree,BTree_Printf* pFunc,int gap,char div)
  181. {
  182. 	TBTree* btree = (TBTree*)tree;
  183. 	if((btree!=NULL)&&(pFunc!=NULL))
  184. 	{
  185. 		recursive_display(btree->root,pFunc,0,gap,div);
  186. 	}
  187. }
  188.  
  189. BTreeNode* BTree_Delete(BTree* tree,BTPos pos,int count)
  190. {
  191. 	BTreeNode* ret = NULL;
  192. 	TBTree* btree = (TBTree*)tree;      //×öÒ»¸ö¿Ç 
  193. 	int bit = 0;
  194. 	if(btree!=NULL)
  195. 	{
  196. 		BTreeNode* parent = NULL;
  197. 		BTreeNode* current = btree->root;
  198. 		while((count>0)&&(current!=NULL))
  199. 		{
  200. 			bit = pos & 1;
  201. 			pos = pos >> 1;
  202. 			
  203. 			parent = current;
  204. 			
  205. 			if(bit==BT_LEFT)
  206. 			{
  207. 				current = current->left;	
  208. 			}	
  209. 			else if(bit==BT_RIGHT)
  210. 			{
  211. 				current = current->right;
  212. 			}
  213. 			count--;
  214. 		}
  215. 		if(parent!=NULL)
  216. 		{
  217. 			if(bit==BT_LEFT)
  218. 			{
  219. 				parent->left = NULL;	
  220. 			}	
  221. 			else if(bit == BT_RIGHT)
  222. 			{
  223. 				parent->right = NULL;	
  224. 			}
  225. 		}
  226. 		else   //the only one node
  227. 		{
  228. 			btree->root = NULL;	
  229. 		}
  230. 		ret = current;    //important
  231. 		
  232. 		btree->count = btree->count - recursive_count(ret);
  233. 	}
  234. 	return ret;
  235. }
  236. BTreeNode* BTree_Get(BTree* tree,BTPos pos,int count)
  237. {
  238. 	BTreeNode* ret = NULL;
  239. 	TBTree* btree = (TBTree*)tree;
  240. 	int bit = 0;
  241. 	if(btree!=NULL)
  242. 	{
  243. 		BTreeNode* parent = NULL;
  244. 		BTreeNode* current = btree->root;
  245. 		
  246. 		while((count>0)&&(current!=NULL))
  247. 		{
  248. 			bit = pos & 1;
  249. 			pos = pos >> 1;	
  250. 			
  251. 			parent = current;      //record the current node
  252. 			
  253. 			if(bit == BT_LEFT)
  254. 			{
  255. 				current = current->left;	
  256. 			}
  257. 			else if(bit == BT_RIGHT)
  258. 			{
  259. 				current = current->right;	
  260. 			}
  261. 			count--;
  262. 		}	
  263. 		ret = current;   //important
  264. 	}
  265. 	return ret;
  266. }
  267.  
  268. BTreeNode* BTree_Root(BTree* tree)
  269. {
  270. 	BTreeNode* ret = NULL;
  271. 	TBTree* btree = (TBTree*)tree;
  272. 	if(btree != NULL)
  273. 	{
  274. 		ret = btree->root;	
  275. 	}
  276. 	return ret;
  277. }
  278.  
  279. int BTree_Height(BTree* tree)
  280. {
  281. 	int ret = 0;
  282. 	TBTree* btree = (TBTree*)tree;
  283. 	if(btree!=NULL)
  284. 	{
  285. 		ret = recursive_height(btree->root);		
  286. 	}
  287. 	return ret;
  288. }
  289. int BTree_Count(BTree* tree)
  290. {
  291. 	int ret = 0;
  292. 	TBTree* btree = (TBTree*)tree;
  293. 	if(btree!=NULL)
  294. 	{
  295. 		ret = btree->count;	
  296. 	}
  297. 	return ret;
  298. }
  299.  
  300. int BTree_Degree(BTree* tree)
  301. {
  302. 	int ret = 0;
  303. 	TBTree* btree = (TBTree*)tree;
  304. 	if(btree!=NULL)
  305. 	{
  306. 		ret = recursive_degree(btree->root);	
  307. 	}
  308. 	return ret;
  309. }




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

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

  

闽ICP备14008679号