不学网

 找回密码
 立即注册

只需一步,快速开始

手机号码,快捷登录

查看: 450|回复: 1

[c/c++] [C数据结构]二叉树

[复制链接]
j2cat 发表于 2018-1-6 19:50:16 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
BTree.h
  1. #ifndef _BTREE_H_
  2. #define _BTREE_H_

  3. #define BT_LEFT 0
  4. #define BT_RIGHT 1

  5. typedef void BTree;

  6. typedef unsigned long long BTPos;

  7. typedef struct _tag_BTreeNode BTreeNode;

  8. struct _tag_BTreeNode {
  9.         BTreeNode* left;
  10.         BTreeNode* right;
  11. };

  12. typedef void(BTree_Printf)(BTreeNode*);

  13. BTree* BTree_Create(void);

  14. void BTree_Destroy(BTree* tree);

  15. void BTree_Clear(BTree* tree);

  16. int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag);

  17. BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count);

  18. BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count);

  19. BTreeNode* BTree_Root(BTree* tree);

  20. int BTree_Height(BTree* tree);

  21. int BTree_Count(BTree* tree);

  22. int BTree_Degree(BTree* tree);

  23. void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div);

  24. #endif
复制代码


BTree.c
  1. #include "BTree.h"
  2. #include <malloc.h>
  3. #include <stdio.h>

  4. typedef struct _tag_BTree TBTree;

  5. struct _tag_BTree {
  6.         int count;
  7.         BTreeNode* root;
  8. };

  9. static int recursive_degree(BTreeNode* root) {
  10.         int ret = 0;

  11.         if (NULL != root) {
  12.                 if (NULL != root->left) {
  13.                         ret++;
  14.                 }
  15.                 if (NULL != root->right) {
  16.                         ret++;
  17.                 }

  18.                 if (1 == ret) {
  19.                         int ld = recursive_degree(root->left);
  20.                         int rd = recursive_degree(root->right);
  21.                         if (ret < ld) {
  22.                                 ret = ld;
  23.                         }
  24.                         if (ret < rd) {
  25.                                 ret = rd;
  26.                         }
  27.                 }
  28.         }
  29.         return ret;
  30. }
  31. static int recursive_height(BTreeNode* root) {
  32.         int ret = 0;

  33.         if (NULL != root) {
  34.                 int lh = recursive_height(root->left);
  35.                 int rh = recursive_height(root->right);
  36.                 ret = ((lh > rh) ? lh : rh) + 1;
  37.         }

  38.         return ret;
  39. }

  40. static int recursive_delete(BTreeNode* node) {
  41.         int ret = 0;
  42.         if (NULL != node) {
  43.                 ret = recursive_delete(node->left) + recursive_delete(node->right) + 1;
  44.         }

  45.         return ret;
  46. }

  47. static void recursive_display(BTreeNode* node, BTree_Printf* pFunc, int format, int gap, char div) {

  48.         if ((NULL != node) && (NULL != pFunc)) {
  49.                 for (int i = 0; i < format; i++) {
  50.                         printf("%c", div);
  51.                 }

  52.                 pFunc(node);
  53.                 printf("\n");
  54.                 if ((NULL != node->left) || (NULL != node->right)) {
  55.                         recursive_display(node->left, pFunc, format + gap, gap, div);
  56.                         recursive_display(node->right, pFunc, format + gap, gap, div);
  57.                 }       
  58.         }
  59.         else {
  60.                         for (int i = 0; i < format; i++) {
  61.                                 printf("%c", div);
  62.                         }
  63.                         printf("\n");
  64.         }
  65. }


  66. BTree* BTree_Create(void) {
  67.         TBTree* ret = (TBTree*)malloc(sizeof(TBTree));

  68.         if (NULL != ret) {
  69.                 ret->count = 0;
  70.                 ret->root = NULL;
  71.         }

  72.         return ret;
  73. }

  74. void BTree_Destroy(BTree* tree) {
  75.         free(tree);
  76. }

  77. void BTree_Clear(BTree* tree) {
  78.         TBTree* btree = (TBTree*)tree;

  79.         if (NULL != btree) {
  80.                 btree->count = 0;
  81.                 btree->root = NULL;
  82.         }
  83. }

  84. int BTree_Insert(BTree* tree, BTreeNode* node, BTPos pos, int count, int flag) {
  85.         TBTree* btree = (TBTree*)tree;
  86.         int ret = (NULL != btree) && (NULL != node) && ((BT_LEFT == flag) || (BT_RIGHT == flag));
  87.         int bit = 0;

  88.         if (ret) {
  89.                 BTreeNode* parent = NULL;
  90.                 BTreeNode* current = btree->root;

  91.                 node->left = NULL;
  92.                 node->right = NULL;

  93.                 while ((count > 0) && (NULL != current)) {
  94.                         bit = pos & 1;
  95.                         pos = pos >> 1;
  96.                        
  97.                         parent = current;

  98.                         if (BT_LEFT == bit) {
  99.                                 current = current->left;
  100.                         }
  101.                         else if(BT_RIGHT == bit) {
  102.                                 current = current->right;
  103.                         }

  104.                         count--;
  105.                 }

  106.                 if (BT_LEFT == flag) {
  107.                         node->left = current;
  108.                 }
  109.                 else if (BT_RIGHT == flag) {
  110.                         node->right = current;
  111.                 }

  112.                 if (NULL != parent) {
  113.                         if (BT_LEFT == bit) {
  114.                                 parent->left = node;
  115.                         }
  116.                         else if (BT_RIGHT == bit) {
  117.                                 parent->right = node;
  118.                         }
  119.                 }
  120.                 else {
  121.                         btree->root = node;
  122.                 }

  123.                 btree->count++;
  124.         }

  125.         return ret;
  126. }

  127. BTreeNode* BTree_Delete(BTree* tree, BTPos pos, int count) {
  128.         TBTree* btree = (TBTree*)tree;
  129.         BTreeNode* ret = NULL;
  130.         int bit = 0;

  131.         if (NULL != btree) {
  132.                 BTreeNode* parent = NULL;
  133.                 BTreeNode* current = btree->root;

  134.                 while ((count > 0) && (NULL != current)) {
  135.                         bit = pos & 1;
  136.                         pos = pos >> 1;

  137.                         parent = current;

  138.                         if (BT_LEFT == bit) {
  139.                                 current = current->left;
  140.                         }
  141.                         else if (BT_RIGHT == bit) {
  142.                                 current = current->right;
  143.                         }
  144.                         count--;
  145.                 }

  146.                 if (NULL != parent) {
  147.                         if (BT_LEFT == bit) {
  148.                                 parent->left = NULL;
  149.                         }
  150.                         else if (BT_RIGHT == bit) {
  151.                                 parent->right = NULL;
  152.                         }
  153.                 }
  154.                 else {
  155.                         btree->root = NULL;
  156.                 }

  157.                 ret = current;
  158.                 btree->count = btree->count - recursive_delete(ret);
  159.         }

  160.         return ret;
  161. }

  162. BTreeNode* BTree_Get(BTree* tree, BTPos pos, int count) {
  163.         TBTree* btree = (TBTree*)tree;
  164.         BTreeNode* ret = NULL;
  165.         int bit = 0;

  166.         if (NULL != btree) {
  167.                 BTreeNode* current = btree->root;

  168.                 while ((count > 0) && (NULL != current)) {
  169.                         bit = pos & 1;
  170.                         pos = pos >> 1;

  171.                         if (BT_LEFT == bit) {
  172.                                 current = current->left;
  173.                         }
  174.                         else if (BT_RIGHT == bit) {
  175.                                 current = current->right;
  176.                         }
  177.                         count--;
  178.                 }
  179.                 ret = current;
  180.         }

  181.         return ret;
  182. }

  183. BTreeNode* BTree_Root(BTree* tree) {
  184.         TBTree* btree = (TBTree*)tree;
  185.         BTreeNode* ret = NULL;
  186.         if (NULL != btree) {
  187.                 ret = btree->root;
  188.         }

  189.         return ret;
  190. }

  191. int BTree_Height(BTree* tree) {
  192.         TBTree* btree = (TBTree*)tree;
  193.         int ret = 0;
  194.         if (NULL != btree) {
  195.                 ret = recursive_height(btree->root);
  196.         }
  197.         return ret;
  198. }


  199. int BTree_Count(BTree* tree) {
  200.         TBTree* btree = (TBTree*)tree;
  201.         int ret = 0;
  202.         if (NULL != btree) {
  203.                 ret = btree->count;
  204.         }

  205.         return ret;
  206. }

  207. int BTree_Degree(BTree* tree) {
  208.         TBTree* btree = (TBTree*)tree;
  209.         int ret = 0;
  210.         if (NULL != btree) {
  211.                 ret = recursive_degree(btree->root);
  212.         }
  213.         return ret;
  214. }

  215. void BTree_Display(BTree* tree, BTree_Printf* pFunc, int gap, char div) {
  216.         TBTree* btree = (TBTree*)tree;
  217.        
  218.         if (NULL != btree) {
  219.                 recursive_display(btree->root, pFunc, 0, gap, div);
  220.         }
  221. }
复制代码
main.c
  1. #include "BTree.h"
  2. #include <stdio.h>
  3. #include <stdlib.h>

  4. typedef struct _tag_Node {
  5.         BTreeNode header;
  6.         char v;
  7. }Node;

  8. void Print_Data(BTreeNode* node) {
  9.         if (NULL != node) {
  10.                 printf("%c", ((Node*)node)->v);
  11.         }
  12. }

  13. int main(void) {

  14.         BTree* tree = BTree_Create();

  15.         Node n1 = { { NULL, NULL }, 'A' };
  16.         Node n2 = { { NULL, NULL }, 'B' };
  17.         Node n3 = { { NULL, NULL }, 'C' };
  18.         Node n4 = { { NULL, NULL }, 'D' };
  19.         Node n5 = { { NULL, NULL }, 'E' };
  20.         Node n6 = { { NULL, NULL }, 'F' };

  21.         BTree_Insert(tree, (BTreeNode*)&n1, 0x0, 0, 0);
  22.         BTree_Insert(tree, (BTreeNode*)&n2, 0x0, 1, 0);
  23.         BTree_Insert(tree, (BTreeNode*)&n3, 0x1, 1, 0);
  24.         BTree_Insert(tree, (BTreeNode*)&n4, 0x0, 2, 0);
  25.         BTree_Insert(tree, (BTreeNode*)&n5, 0x2, 2, 0);
  26.         BTree_Insert(tree, (BTreeNode*)&n6, 0x2, 3, 0);

  27.         printf("Degree: %d \n", BTree_Degree(tree));
  28.         printf("Height: %d \n", BTree_Height(tree));
  29.         printf("Count: %d \n", BTree_Count(tree));
  30.         BTree_Display(tree, Print_Data, 4, '-');

  31.         printf("position At(0x2, 2): %c\n", ((Node*)BTree_Get(tree, 0x02, 2))->v);

  32.         printf("After Delete B:\n");
  33.         BTree_Delete(tree, 0x0, 1);
  34.         printf("Degree: %d \n", BTree_Degree(tree));
  35.         printf("Height: %d \n", BTree_Height(tree));
  36.         printf("Count: %d \n", BTree_Count(tree));
  37.         BTree_Display(tree, Print_Data, 4, '-');

  38.         BTree_Clear(tree);
  39.         printf("After Clear:\n");
  40.         printf("Degree: %d \n", BTree_Degree(tree));
  41.         printf("Height: %d \n", BTree_Height(tree));
  42.         printf("Count: %d \n", BTree_Count(tree));
  43.         BTree_Display(tree, Print_Data, 4, '-');

  44.         BTree_Destroy(tree);
  45.         system("pause");
  46.         return 0;
  47. }
复制代码


回复

使用道具 举报

64k 发表于 2018-1-18 09:56:53 | 显示全部楼层
有点难以懂
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|手机版|小黑屋|不学网

GMT+8, 2018-9-19 04:59

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表