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

二叉查找树及其C语言实现详解_二叉树的查找c语言

作者：码创造者 | 2024-07-18 16:04:51

赞

踩

二叉树的查找c语言

目录

一、树（Tree）

二、二叉树

1、概念

2、二叉树的存储方式

3、二叉树的遍历

三、二叉查找树

1、查找操作

2、插入操作

3、删除操作

4、修改操作

          5、节点清空和树销毁操作

四、支持重复数据的二叉查找树

1、每个节点存储多个对象数据

2、每个节点存储单个对象数据

五、二叉查找树C语言实现

1、数据结构

2、操作函数声明

3、具体实现

4、调试问题

六、说明

一、树（Tree）

树是一种一种非线性表结构。如下图，A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。B、C、D 这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。我们把没有父节点的节点叫作根节点，也就是图中的节点 E。我们把没有子节点的节点叫作叶子节点或者叶节点，比如图中的 G、H、I、J、K、L 都是叶子节点

 

  • 节点的高度（Height）：节点到叶子节点的最长路径（边数），从下往上
  • 节点深度（Depth）：根节点到这个节点的的最长路径（边数），从上往下
  • 节点的层（Level）数：节点的深度+1

数的高度：根节点的高度

二、二叉树

1、概念

每个节点最多只有2个子节点的树，这两个子节点分别为左子节点和右子节点。

满二叉树：叶子节点全部在最底层，除了叶子节点外，每个节点都有左右两个子节点

完全二叉树：叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大

2、二叉树的存储方式

基于链表的链式存储：每个节点需要额外的2个指针来存储左右节点地址

基于数组的顺序存储：每个节点不需要额外的子节点指针，左子节点存储在下标 2 * i 的位置，右子节点存储在 2 * i + 1的位置，i为节点的层数。但如果是非完全二叉树也会比较浪费空间。

3、二叉树的遍历

根据节点和他的左右节点遍历的先后顺序，可分为前序遍历、中序遍历、后续遍历

  • 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。本身 ---> 左 ---> 右
  • 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。左 ---> 本身 ---> 右
  • 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。 左 ---> 右 ---> 本身

三、二叉查找树

一种能够快速查找、插入、删除数据的特殊二叉树结构。二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值，非平衡的二叉树

1、查找操作

二叉查找树可以快速的查找最大节点和最小节点；按照中序遍历二叉查找树，可以输出有序的数据序列，时间复杂度为O(n)，非常高效。

查找指定节点步骤：

第一步：先取根节点，如果根节点数据 = 要查找的数据，则直接返回，否则进入第二步

第二步：如果查找的数比根节点小，则在左子树中递归查找

第三部：如果查找的数比根节点大，则在右子数中递归查找

查找最小节点步骤：

遍历二叉树的左子树，直到左节点为NULL的节点即为最小节点

查找最大节点步骤：

遍历二叉树的右子树，直到右节点为NULL的节点即为最大节点

中序遍历步骤：

对于树中的任意节点来说，先拷贝它的左子树节点数据至双向链表中，然后再拷贝它本身节点数据双向链表中，最后拷贝它的右子树节点数据双向链表中。左 ---> 本身 ---> 右

 

2、插入操作

插入操作与查找过程类似，一般新插入的数据都是在叶子节点上；所以也是先取根节点

第一步：如果查找数据比节点数据大，且节点的右子节点为空，则将数据直接插入右子节点的位置；如果右子节点不为空，则再递归遍历右子数，查找插入位置。

第二步：如果查找数据比节点数据小，且节点的左子节点为空，则将数据直接插入左子节点的位置；如果左子节点不为空，则再递归遍历左子数，查找插入位置。

3、删除操作

先说明下：del为删除节点、f_del为删除节点的父节点、min为最小节点、f_min为最小节点的父节点

第一种情况：如果删除的节点没有子节点，只需要直接将删除节点父节点中，指向要删除的子节点（删除节点）置为空。如图中要删除的55

第二种情况：如果删除的节点只有一个子节点（只有左节点或只有右节点），则只需要更新删除节点的父节点中指向要删除节点的指针，让其指向要删除节点的子节点。如图中要删除的13，有4种细分情况：

1、del只有左节点，del为f_del的左节点，删除过程为：将f_del左节点指向del的左节点，再将del删除

2、del只有左节点，del为f_del的右节点，删除过程为：将f_del右节点指向del的左节点，再将del删除

3、del只有右节点，del为f_del的左节点，删除过程为：将f_del左节点指向del的右节点，再将del删除

4、del只有右节点，del为f_del的右节点，删除过程为：将f_del右节点指向del的右节点，再将del删除

第三种情况：如果删除的节点有两个子节点，则需要找到该节点的右子树中最小的节点，把他替换到要删除的节点上，然后删除这个最小节点。如图要删除的18，有有4种细分情况：

1、f_min就为del，min为叶子节点，删除过程为：先将min的数据替换到del，再将f_min的右节点指向min的右节点（NULL），最后删除min

2、f_min就为del，min还有右子树（不会再有左子树），删除过程为：先将min的数据替换到del，再将f_min的右节点指向min的右节点（！NULL），最后删除min

3、f_min不为del，min为叶子节点，删除过程为：先将min的数据替换到del，再将f_min的左节点指向min的右节点（NULL），最后删除min

4、f_min不为del，min还有右子树（不会再有左子树），删除过程为：先将min的数据替换到del，再将f_min的左节点指向min的右节点（！NULL），最后删除min

4、修改操作

修改操作与查找操作类似，在查找到相同key值的节点后，先释放节点指向的数据空间，然后修改节点数据。在修改过程中需要注意：

1、会先释放节点指向的就数据空间(这里如果是realloc更大的数据空间,容易造成指针泄露,且是不知道整个数据结构的大小的) 

2、修改的节点必须为新动态分配的空间

3、如果修改的节点有多个key值相同的节点,只会修改最新查找的一个

 

5、节点清空和树销毁操作

有的时候需要清空二叉树的所有节点保留树的句柄，再插入新的节点时不用再重新创建一颗新的树。或是不需要使用到树时时候需要释放所有内存，就需要将整颗树销毁，下次使用的时候再重新申请新的树。

使用递归的方法，可以将树的所有节点删除，递归的终止条件就是节点为空，递归公式为，递归查找到左子树和右子树均为空的树节点，先将该节点指向的数据删除（如果指向的数据为动态分配的需要在这里释放），再释放节点空间，最后将节点指向空（这里需要注意指针变量传参，如果要修改该指针变量的值即指针本身需要传入指针变量的地址，即使用双重指针才能！！！）

 

 

四、支持重复数据的二叉查找树

在工程中使用二叉查找树时，用来存储单个数据的情况很少，多用来存储包含多个字段的对象，利用对象的某个字段作为key值来构建key-value的数据存储结构。在key-value的数据存储结构中，就不可避免的会有相同key值的情况，在插入新的节点时，如何存储相同key值的对象？大致有以下两种方法

1、每个节点存储多个对象数据

在二叉查找树的每一个节点使用链表来存储key值相同的对象，相对容易理解，但是这样的弊端就是二叉树的每个节点中至少需要多3个地址空间用来存储 链表的节点数据，比较浪费空间。

2、每个节点存储单个对象数据

在插入数据时，如果key值与二叉树的某个节点key值相同，则将数据插入到这个相同key值节点的右子树。与不支持重复数据二叉树插入操作相比，只需要将 > key值得节点插入到这个节点的右子数改为 >= 即可实现

 

在查找数据时，查找key值相同的节点后，并不停止查找，而是继续在右子树中查找，直到遇到叶子节点为止，然后将节点数据放入链表中，这样可以把key值相同的所有数据都找出来。

 

在删除数据时，删除节点只有左子树时则直接退出，因为没有右子树就不会有相同的key节点。删除节点右子树不为空 或 右子树节点为空但是key值相同 则继续查找相同key值的节点

 

 

五、二叉查找树C语言实现

1、数据结构

  1. #define BS_TREE_MALLOC(size)    pvPortMalloc(size);
  2. #define BS_TREE_REALLOC(p,size) rt_realloc(p,size);
  3. #define BS_TREE_CALLOC(n,size)  calloc(n,size);
  4. #define BS_TREE_FREE(p)         vPortFree(p);
  5.  
  6. struct bs_tree_node;
  7. struct bs_tree;
  8.  
  9. /* 
  10.  * 二叉查找树key比较, key_cmp:传入的要比较的key, key_becmp:被比较的key
  11.  * 任意一个节点，其左子树中任意一个节点的值，都要小于这个节点的值
  12.  * 任意一个几点，其右子数中任意一个节点的值，都要大于这个节点的值
  13.  * 返回值 > 0 : key_cmp > key_becmp
  14.  * 返回值 = 0 : key_cmp = key_becmp
  15.  * 返回值 < 0 : key_cmp < key_becmp
  16. */
  17. typedef int (*bstree_keycmp)(struct bs_tree *bstree, const void *key_cmp, const void *key_becmp);
  18. /* 二叉树中的节点数据删除函数,如果插入节点为动态分配,则需要在该函数中释放节点空间 */
  19. typedef int (*bstree_value_free)(struct bs_tree_node *node);
  20.  
  21. struct bs_tree_node
  22. {
  23.     void *key;
  24.     void *value;
  25.     struct bs_tree_node *left_child;  /*左子树*/
  26.     struct bs_tree_node *right_child; /*右子树*/
  27. };
  28.  
  29. struct bs_tree
  30. {
  31.     int num;                        /*二叉树中节点个数的总和*/
  32.     struct bs_tree_node *root;      /*二叉树的根节点*/
  33.     bstree_keycmp        keycmp;    /*二叉树key比较*/
  34.     bstree_value_free    valuefree; /*二叉树节点数据删除*/
  35. };
  36.  
  37. #define BSTREE_IS_EMPTY(tree) (tree->num == 0)
  38.  
  39. /*根据当前结构体元素的地址，获取到结构体首地址*/
  40. //#define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
  41. //#define container(ptr,type,member) ({\
  42. //  const typeof( ((type *)0)->member) *__mptr = (ptr);\
  43. //  (type *) ((char *)__mptr - OFFSETOF(type,member));})
  44.  
  45. #define OFFSETOF(TYPE,MEMBER) ((unsigned int)&((TYPE *)0)->MEMBER)
  46. #define container(ptr,type,member) ((type *) ((char *)ptr - OFFSETOF(type,member)))

2、操作函数声明

  1. extern struct bs_tree *bs_tree_creat(bstree_keycmp keycmp, bstree_value_free valuefree);
  2. extern struct bs_tree *bs_tree_creat_default(bstree_value_free valuefree);
  3. extern int    bs_tree_insert(struct bs_tree *bstree, void *key, void *value);
  4. extern int    bs_tree_delete(struct bs_tree *bstree, void *key);
  5. extern int    bs_tree_modify(struct bs_tree *bstree, void *key, void *value);
  6. extern int    bs_tree_search(struct bs_tree *bstree, void *key, struct double_list *dlist);
  7. extern void * bs_tree_search_min(struct bs_tree *bstree);
  8. extern void * bs_tree_search_max(struct bs_tree *bstree);
  9. extern void   bs_tree_node_empty(struct bs_tree **bstree, struct bs_tree_node **node);
  10. extern void   bs_tree_destroy   (struct bs_tree **bstree);
  11.  
  12. /*中序遍历二叉树，并将节点数据放入双向链表中，链表在使用完释放空间的时候，不能将节点数据空间删除*/
  13. extern int bs_tree_inorder(struct bs_tree *bstree, struct bs_tree_node *node, struct double_list *dlist);
  14.  
  15. extern void bs_tree_sample(void);

3、具体实现

  1. #include "algo_bs_tree.h"
  2.  
  3.  
  4. /**
  5.  * 二叉树key比较, key_cmp:传入的要比较的key, key_becmp:被比较的key
  6.  * 
  7.  * @return > 0 : key_cmp > key_becmp
  8.  * @return = 0 : key_cmp = key_becmp
  9.  * @return < 0 : key_cmp < key_becmp
  10.  * 
  11.  */
  12. static int bstree_keycmp_default(struct bs_tree *bstree, const void *key_cmp, const void *key_becmp)
  13. {
  14.     return strcmp(key_cmp, key_becmp);
  15. }
  16.  
  17. /**
  18.  * 动态创建一个二叉查找树.
  19.  * 
  20.  * @return NULL:创建失败
  21.  *        !NULL:创建成功
  22.  */
  23. struct bs_tree *bs_tree_creat(bstree_keycmp keycmp, bstree_value_free valuefree)
  24. {
  25.     struct bs_tree *bstree = NULL;
  26.  
  27.     if (keycmp == NULL)
  28.         return NULL;
  29.  
  30.     /*申请二叉查找树结构空间*/
  31.     bstree = BS_TREE_MALLOC(sizeof(*bstree));
  32.     if (bstree == NULL)
  33.         return NULL;
  34.  
  35.     bstree->num       = 0;
  36.     bstree->keycmp    = keycmp;
  37.     bstree->valuefree = valuefree;
  38.     bstree->root      = NULL;
  39.     
  40.     return bstree;
  41. }
  42.  
  43. /**
  44.  * 使用默认 key比较函数 动态创建一个二叉查找树.
  45.  * 
  46.  * @return NULL:创建失败
  47.  *        !NULL:创建成功
  48.  */
  49. struct bs_tree *bs_tree_creat_default(bstree_value_free valuefree)
  50. {
  51.     return bs_tree_creat(bstree_keycmp_default, valuefree);
  52. }
  53.  
  54.  
  55. /**
  56.  * 向一个二叉查找树插入一个节点.支持相同key值的节点插入
  57.  * 
  58.  * @param bstree: 二叉查找树
  59.  * @param key: 关键值
  60.  * @param value: 节点数据
  61.  * 
  62.  * @return 0:插入成功
  63.  *        -1:二叉查找树不存在 或 key为空 或 value为空
  64.  *        -2:节点空间申请失败
  65.  *        -3:插入失败
  66.  */
  67. int bs_tree_insert(struct bs_tree *bstree, void *key, void *value)
  68. {
  69.     struct bs_tree_node *new_node = NULL;
  70.     struct bs_tree_node *f_node = NULL;
  71.     int res = 0;
  72.  
  73.     if (bstree == NULL || key == NULL || value == NULL)
  74.         return -1;
  75.  
  76.     /*申请二叉查找树节点空间*/
  77.     new_node = (struct bs_tree_node*)BS_TREE_MALLOC(sizeof(*new_node));
  78.     if (new_node == NULL)
  79.         return -2;
  80.     
  81.     new_node->key = key;
  82.     new_node->value = value;
  83.     new_node->left_child = NULL;
  84.     new_node->right_child = NULL;
  85.     
  86.     /*数为空，插入到根节点*/
  87.     if (BSTREE_IS_EMPTY(bstree))
  88.     {
  89.         bstree->root = new_node;
  90.         bstree->num ++;
  91.         return 0;
  92.     }
  93.     else
  94.     {
  95.         f_node = bstree->root;
  96.         while (f_node != NULL)
  97.         {
  98.             res = bstree->keycmp(bstree, key, f_node->key);
  99.             if (res >= 0) /*去右子树中查找,支持相同key值的节点插入*/
  100.             {
  101.                 if (f_node->right_child == NULL)
  102.                 {
  103.                     f_node->right_child = new_node;
  104.                     bstree->num ++;
  105.                     return 0;
  106.                 }
  107.                 f_node = f_node->right_child;
  108.             }
  109.             else if (res < 0)/*去左子树中查找*/
  110.             {
  111.                 if (f_node->left_child == NULL)
  112.                 {
  113.                     f_node->left_child = new_node;
  114.                     bstree->num ++;
  115.                     return 0;
  116.                 }
  117.                 f_node = f_node->left_child;
  118.             }
  119.         }
  120.     }
  121.  
  122.     return -3;
  123. }
  124.  
  125.  
  126. /**
  127.  * 删除一个节点.
  128.  * 
  129.  * @param bstree: 二叉查找树
  130.  * @param key: 删除节点关键值
  131.  * 
  132.  * @return 0:删除成功
  133.  *        -1:二叉查找树不存在 或 key为空
  134.  *        -2:节点不存在
  135.  */
  136. int bs_tree_delete(struct bs_tree *bstree, void *key)
  137. {
  138.     struct bs_tree_node *del_node = NULL;//要删除节点
  139.     struct bs_tree_node *f_delnode = NULL;//要删除节点的父节点
  140.     struct bs_tree_node *minnode = NULL;//最小节点
  141.     struct bs_tree_node *f_minnode = NULL;//最小节点的父节点
  142.     struct bs_tree_node *temp = NULL;
  143.     int finsh_flg = 0, res = 0;
  144.  
  145.     if (bstree == NULL || key == NULL)
  146.         return -1;
  147.     
  148.     /*查找要删除的节点*/
  149.     del_node = bstree->root;
  150.     while ((del_node != NULL) && ((res = bstree->keycmp(bstree, key, del_node->key)) != 0))
  151.     {
  152.         f_delnode = del_node;
  153.         if (res > 0)
  154.         {
  155.             del_node = del_node->right_child;
  156.         }
  157.         else
  158.         {
  159.             del_node = del_node->left_child;
  160.         }
  161.     }
  162.  
  163.     /*要删除的节点不存在*/
  164.     if (del_node == NULL)
  165.         return -2;
  166.  
  167.     do
  168.     {           
  169.         if (bstree->keycmp(bstree, key, del_node->key) == 0)
  170.         {
  171.             /*如果删除的节点有两个子节点，则需要找到该节点的右子树中最小的节点，把他替换到要删除的节点上，然后删除这个最小节点
  172.             *
  173.             *1、f_min就为del，min为叶子节点，删除过程为：先将min的数据替换到del，再将f_min的右节点指向min的右节点（NULL），最后删除min
  174.             *2、f_min就为del，min还有右子树（不会再有左子树），删除过程为：先将min的数据替换到del，再将f_min的右节点指向min的右节点（！NULL），最后删除min
  175.             *3、f_min不为del，min为叶子节点，删除过程为：先将min的数据替换到del，再将f_min的左节点指向min的右节点（NULL），最后删除min
  176.             *4、f_min不为del，min还有右子树（不会再有左子树），删除过程为：先将min的数据替换到del，再将f_min的左节点指向min的右节点（！NULL），最后删除min
  177.             */
  178.             if ((del_node->left_child != NULL) && (del_node->right_child != NULL))
  179.             {
  180.                 f_minnode = del_node;
  181.                 minnode = del_node->right_child;
  182.                 while (minnode->left_child != NULL)//查找最小节点
  183.                 {
  184.                     f_minnode = minnode;
  185.                     minnode = minnode->left_child;
  186.                 }
  187.  
  188.                 /*先删除要删除节点上的数据,数据空间为动态申请的需要在这里先释放*/
  189.                 bstree->valuefree(del_node);
  190.  
  191.                 del_node->key = minnode->key;
  192.                 del_node->value = minnode->value;
  193.                 if (f_minnode == del_node)
  194.                 {
  195.                     f_minnode->right_child = minnode->right_child;
  196.                 }
  197.                 else
  198.                 {
  199.                     f_minnode->left_child = minnode->right_child;
  200.                 }
  201.  
  202.                 /*交换最小节点和删除节点,因为真正删除的是最小节点,
  203.                 删除节点的父节点的子节点还是删除节点*/
  204.                 temp = minnode;
  205.                 minnode = del_node;
  206.                 del_node = temp;
  207.             }
  208.             /*要删除的节点只有左子树*/
  209.             else if (del_node->left_child != NULL)
  210.             {
  211.                 /*先删除要删除节点上的数据,数据空间为动态申请的需要在这里先释放*/
  212.                 bstree->valuefree(del_node);
  213.                 
  214.                 minnode = del_node->left_child;
  215.  
  216.                 finsh_flg = 1;
  217.             }
  218.             /*要删除的节点只有右子树*/
  219.             else if (del_node->right_child != NULL)
  220.             {
  221.                 /*先删除要删除节点上的数据,数据空间为动态申请的需要在这里先释放*/
  222.                 bstree->valuefree(del_node);
  223.  
  224.                 minnode = del_node->right_child;
  225.             }
  226.             /*要删除节点没有子节点*/
  227.             else
  228.             {
  229.                 /*先删除要删除节点上的数据,数据空间为动态申请的需要在这里先释放*/
  230.                 bstree->valuefree(del_node);
  231.  
  232.                 minnode->left_child = NULL;
  233.                 minnode->right_child = NULL;
  234.                 minnode = NULL;
  235.             }
  236.  
  237.             if (del_node == bstree->root)//删除的是头结点
  238.             {
  239.                 bstree->root = minnode;
  240.             }
  241.             else
  242.             {
  243.                 if (del_node == f_delnode->left_child)//删除节点在删除节点父节点的左子树上
  244.                 {
  245.                     f_delnode->left_child = minnode;
  246.                 }
  247.                 else if (del_node == f_delnode->right_child)//删除节点在删除节点父节点的右子树上
  248.                 {
  249.                     f_delnode->right_child = minnode;
  250.                 }
  251.             }
  252.  
  253.             BS_TREE_FREE(del_node);
  254.             del_node = minnode;/*将删除节点指向填补的节点,继续判断删除节点的右子树是否还有相同key值的节点*/
  255.  
  256.             bstree->num --;    
  257.         }
  258.         else
  259.         {
  260.             del_node = del_node->right_child;/*右子树不为空但key不相同*/
  261.         }
  262.                 
  263.     /*1、删除节点只有左子树时则直接退出,因为没有右子树就不会有相同的key节点
  264.       2、删除节点右子树不为空 或 右子树节点为空但是key值相同 则继续查找相同key值的节点
  265.     */
  266.     } while ( ((del_node->right_child != NULL) || ((del_node->right_child == NULL) && (bstree->keycmp(bstree, key, del_node->key) == 0))) && !finsh_flg);
  267.       
  268.     return 0;
  269. }
  270.  
  271. /**
  272.  * 修改一个节点.注意事项:
  273.  * 1、会先释放节点指向的就数据空间(这里如果是realloc更大的数据空间,容易造成指针泄露,且是不知道整个数据结构的大小的) 
  274.  * 2、修改的节点必须为新动态分配的空间
  275.  * 3、如果修改的节点有多个key值相同的节点,只会修改最新查找的一个
  276.  *
  277.  * @param bstree: 二叉查找树
  278.  * @param key: 修改节点关键值
  279.  * @param value: 修改节点数据
  280.  * 
  281.  * @return 0:修改成功
  282.  *        -1:二叉查找树不存在 或 key为空 或value为空
  283.  *        -2:节点不存在
  284.  */
  285. int bs_tree_modify(struct bs_tree *bstree, void *key, void *value)
  286. {
  287.     struct bs_tree_node *mody_node = NULL;
  288.     int res = -2;
  289.     
  290.     if (bstree == NULL || key == NULL || value == NULL)
  291.         return -1;
  292.  
  293.     /*查找要修改的节点*/
  294.     mody_node = bstree->root;
  295.     while (mody_node != NULL)
  296.     {
  297.         res = bstree->keycmp(bstree, key, mody_node->key);
  298.         if (res > 0)
  299.         {
  300.             mody_node = mody_node->right_child;
  301.         }
  302.         else if (res < 0)
  303.         {
  304.             mody_node = mody_node->left_child;
  305.         }
  306.         else
  307.         {
  308.             bstree->valuefree(mody_node);   
  309.             mody_node->key = key;
  310.             mody_node->value = value;
  311.             res = 0;
  312.             break;
  313.         }
  314.     }
  315.  
  316.     return res;
  317. }
  318.  
  319. /**
  320.  * 根据key查找节点数据.
  321.  * 
  322.  * @param bstree: 二叉查找树
  323.  * @param key: 查找节点关键值
  324.  * 
  325.  * @return 0:查找成功
  326.  *        -1:二叉查找树不存在 或 key为空 或value为空
  327.  *        -2:节点不存在
  328.  */
  329. int bs_tree_search(struct bs_tree *bstree, void *key, struct double_list *dlist)
  330. {
  331.     struct bs_tree_node *ser_node = NULL;
  332.     int res = -2;
  333.     
  334.     if (bstree == NULL || key == NULL || BSTREE_IS_EMPTY(bstree))
  335.         return -1;
  336.  
  337.     /*查找要查找的节点*/
  338.     ser_node = bstree->root;
  339.     while (ser_node != NULL)
  340.     {
  341.         res = bstree->keycmp(bstree, key, ser_node->key);
  342.         if (res > 0)
  343.         {
  344.             ser_node = ser_node->right_child;
  345.         }
  346.         else if (res < 0)
  347.         {
  348.             ser_node = ser_node->left_child;
  349.         }
  350.         else
  351.         {
  352.             double_list_add_node_tail(dlist, ser_node->value);
  353.             ser_node = ser_node->right_child;
  354.             res = 0;
  355.         }
  356.     }
  357.  
  358.     return res;
  359. }
  360.  
  361. /**
  362.  * 查找二叉树中的最小节点数据.
  363.  * 
  364.  * @param bstree: 二叉查找树
  365.  * 
  366.  * @return 0:查找成功
  367.  *        -1:二叉查找树不存在 或 key为空 或value为空
  368.  *        -2:节点不存在
  369.  */
  370. void * bs_tree_search_min(struct bs_tree *bstree)
  371. {
  372.     struct bs_tree_node *ser_node = NULL;
  373.     
  374.     if (bstree == NULL || BSTREE_IS_EMPTY(bstree))
  375.         return NULL;
  376.  
  377.     /*查找要查找的节点*/
  378.     ser_node = bstree->root;
  379.     while ((ser_node != NULL) && (ser_node->left_child != NULL))
  380.     {
  381.         ser_node = ser_node->left_child;
  382.     }
  383.  
  384.     if (ser_node != NULL)
  385.     {
  386.         return ser_node->value;
  387.     }
  388.  
  389.     return NULL;
  390. }
  391.  
  392. /**
  393.  * 查找二叉树中的最大节点数据.
  394.  * 
  395.  * @param bstree: 二叉查找树
  396.  * 
  397.  * @return 0:查找成功
  398.  *        -1:二叉查找树不存在 或 key为空 或value为空
  399.  *        -2:节点不存在
  400.  */
  401. void * bs_tree_search_max(struct bs_tree *bstree)
  402. {
  403.     struct bs_tree_node *ser_node = NULL;
  404.     
  405.     if (bstree == NULL || BSTREE_IS_EMPTY(bstree))
  406.         return NULL;
  407.  
  408.     /*查找要查找的节点*/
  409.     ser_node = bstree->root;
  410.     while ((ser_node != NULL) && (ser_node->right_child != NULL))
  411.     {
  412.         ser_node = ser_node->right_child;
  413.     }
  414.  
  415.     if (ser_node != NULL)
  416.     {
  417.         return ser_node->value;
  418.     }
  419.  
  420.     return NULL;
  421. }
  422.  
  423. /**
  424.  * 中序遍历二叉树,并将节点数据放入双向链表中
  425.  * 
  426.  * @param bstree: 二叉查找树
  427.  * 
  428.  * @return NULL:查找失败
  429.  *        !NULL:查找成功.返回节点数据
  430.  */
  431. int bs_tree_inorder(struct bs_tree *bstree, struct bs_tree_node *node, struct double_list *dlist)
  432. {    
  433.     if (bstree == NULL || BSTREE_IS_EMPTY(bstree))
  434.         return NULL;
  435.  
  436.     if (node == NULL)
  437.     {
  438.         return NULL;
  439.     }
  440.  
  441.     bs_tree_inorder(bstree, node->left_child, dlist);
  442.     double_list_add_node_tail(dlist, node->value);
  443.     bs_tree_inorder(bstree, node->right_child, dlist);
  444.  
  445.     return dlist->len;
  446. }
  447.  
  448. ///**
  449. // * 清空二叉树节点数据
  450. // * 
  451. // * @param bstree: 二叉查找树
  452. // * 
  453. // * @return 
  454. // */
  455. //void bs_tree_node_empty(struct bs_tree *bstree, struct bs_tree_node *node)
  456. //{
  457. //    if (bstree == NULL || BSTREE_IS_EMPTY(bstree))
  458. //        return;
  459.  
  460. //    if (node == NULL)
  461. //    {
  462. //        return;
  463. //    }
  464.  
  465. //    bs_tree_node_empty(bstree, node->left_child);
  466. //    bs_tree_node_empty(bstree, node->right_child);
  467. //    bstree->valuefree(node);
  468. //    BS_TREE_FREE(node);
  469. //  node = NULL;
  470.     bstree->num--;
  471. //}
  472.  
  473. ///**
  474. // * 销毁一颗二叉查找树
  475. // * 
  476. // * @param bstree: 二叉查找树
  477. // * 
  478. // * @return 
  479. // */
  480. //void bs_tree_destroy(struct bs_tree *bstree)
  481. //{
  482. //    bs_tree_node_empty(bstree, bstree->root);
  483. //    BS_TREE_FREE(bstree);
  484. //}
  485.  
  486. /**
  487.  * 清空二叉树节点数据
  488.  * 
  489.  * @param bstree: 二叉查找树
  490.  * 
  491.  * @return 
  492.  */
  493. void bs_tree_node_empty(struct bs_tree **bstree, struct bs_tree_node **node)
  494. {
  495.     if (*bstree == NULL || BSTREE_IS_EMPTY((*bstree)))
  496.         return;
  497.  
  498.     if (*node == NULL)
  499.     {
  500.         return;
  501.     }
  502.  
  503.     bs_tree_node_empty(bstree, &(*node)->left_child);
  504.     bs_tree_node_empty(bstree, &(*node)->right_child);
  505.     (*bstree)->valuefree(*node);
  506.     (*bstree)->num--;
  507.     BS_TREE_FREE(*node);
  508.     *node = NULL;
  509. }
  510.  
  511. /**
  512.  * 销毁一颗二叉查找树
  513.  * 
  514.  * @param bstree: 二叉查找树
  515.  * 
  516.  * @return 
  517.  */
  518. void bs_tree_destroy(struct bs_tree **bstree)
  519. {
  520.     bs_tree_node_empty(bstree, &(*bstree)->root);
  521.     BS_TREE_FREE(*bstree);
  522.     *bstree = NULL;
  523. }
  524.  
  525. /*******************************************************************************************
  526.  *                                          使用示例
  527.  *******************************************************************************************/
  528. struct test_node
  529. {
  530.     char key[10];
  531.     char value[10];
  532. };
  533.  
  534. static int node_value_free_sample(struct bs_tree_node *node)
  535. {
  536.     struct test_node *node_temp = NULL;
  537.  
  538.     /*根据key在test_node结构体中的偏移地址,找到二叉查找树节点实际指向的结构体首地址*/
  539.     node_temp = container(node->key, struct test_node, key);
  540.     /*如果节点所指向数据空间为动态申请的则需要释放*/
  541.     BS_TREE_FREE(node_temp);
  542.     /*将二叉树中指向这块内存的节点key 和 value 赋为空*/
  543.     node->key = NULL;
  544.     node->value = NULL;
  545.     
  546.     return 0;
  547. }
  548.  
  549.  
  550. struct bs_tree *bs_tree_test = NULL;
  551. char tree_node_read[10][10];
  552. struct double_list *dlist_test = NULL;
  553.  
  554. void bs_tree_sample(void)
  555. {
  556.     int i = 0, j = 0, key[10] = {0};
  557.     struct test_node *node_temp = NULL;
  558.     char rd_key[10] = {10}, del_key[10] = {0};
  559.     struct double_list_node *dlist_node = NULL;
  560.  
  561.     bs_tree_test = bs_tree_creat_default(node_value_free_sample);
  562.     dlist_test = double_list_creat();
  563.     
  564.     for (i=0; i<10; i++)
  565.     {
  566.         key[i] = rand() % 10;
  567.     }
  568.     
  569.     /*插入 -- 查询*/
  570.     for (i=0; i<10; i++)
  571.     {
  572.         node_temp = BS_TREE_MALLOC(sizeof(*node_temp));
  573.         memset(node_temp, 0, sizeof(*node_temp));
  574.         sprintf(node_temp->key, "AAA%d", key[i]);
  575.         sprintf(node_temp->value, "%d", key[i]);
  576.         bs_tree_insert(bs_tree_test, node_temp->key, node_temp->value);//支持多个节点插入
  577.     }
  578.     for (i=0; i<10; i++)
  579.     {
  580.         memset(tree_node_read[i], 0, 10);
  581.         memset(rd_key, 0, sizeof(rd_key));
  582.         sprintf(rd_key, "AAA%d", key[i]);
  583.         
  584.         bs_tree_search(bs_tree_test, rd_key, dlist_test);//相同key值的数据会被放入双向链表中
  585.         dlist_node = dlist_test->head;
  586.         for (j=0; j<dlist_test->len; j++)//相同key值的节点数据
  587.         {
  588.             memcpy(tree_node_read[j], dlist_node->value, 10);
  589.             dlist_node = dlist_node->next;
  590.         }
  591.         double_list_node_empty(dlist_test, 0);//清空双向链表节点
  592.     }
  593.     
  594.     /*中序遍历*/
  595.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);
  596.     dlist_node = dlist_test->head;
  597.     for (i=0; i<dlist_test->len; i++)
  598.     {
  599.         memcpy(tree_node_read[i], dlist_node->value, 10);
  600.         dlist_node = dlist_node->next;
  601.     }
  602.     double_list_node_empty(dlist_test, 0);
  603.     
  604.     
  605.     
  606.     /*清空 -- 插入 -- 查询*/
  607.     bs_tree_node_empty(&bs_tree_test, &(bs_tree_test)->root);
  608.     for (i=0; i<10; i++)
  609.     {
  610.         node_temp = BS_TREE_MALLOC(sizeof(*node_temp));
  611.         memset(node_temp, 0, sizeof(*node_temp));
  612.         sprintf(node_temp->key, "AAA%d", key[i]);
  613.         sprintf(node_temp->value, "%d", key[i] + 10);
  614.         bs_tree_insert(bs_tree_test, node_temp->key, node_temp->value);
  615.     }
  616.     for (i=0; i<10; i++)
  617.     {
  618.         memset(tree_node_read[i], 0, 10);
  619.         memset(rd_key, 0, sizeof(rd_key));
  620.         sprintf(rd_key, "AAA%d", key[i]);
  621.         
  622.         bs_tree_search(bs_tree_test, rd_key, dlist_test);//相同key值的数据会被放入双向链表中
  623.         dlist_node = dlist_test->head;
  624.         for (j=0; j<dlist_test->len; j++)//相同key值的节点数据
  625.         {
  626.             memcpy(tree_node_read[j], dlist_node->value, 10);
  627.             dlist_node = dlist_node->next;
  628.         }
  629.         double_list_node_empty(dlist_test, 0);//清空双向链表节点
  630.     }
  631.     /*中序遍历*/
  632.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);
  633.     dlist_node = dlist_test->head;
  634.     for (i=0; i<dlist_test->len; i++)
  635.     {
  636.         memcpy(tree_node_read[i], dlist_node->value, 10);
  637.         dlist_node = dlist_node->next;
  638.     }
  639.     double_list_node_empty(dlist_test, 0);
  640.     
  641.     
  642.     
  643.     /*修改 -- 查询*/
  644.     for (i=0; i<10; i++)
  645.     {
  646.         node_temp = BS_TREE_MALLOC(sizeof(*node_temp));
  647.         memset(node_temp, 0, sizeof(*node_temp));
  648.         sprintf(node_temp->key, "AAA%d", key[i]);
  649.         sprintf(node_temp->value, "%d", key[i] + 20);
  650.         bs_tree_modify(bs_tree_test, node_temp->key, node_temp->value);
  651.     }
  652.     for (i=0; i<10; i++)
  653.     {
  654.         memset(tree_node_read[i], 0, 10);
  655.         memset(rd_key, 0, sizeof(rd_key));
  656.         sprintf(rd_key, "AAA%d", key[i]);
  657.         
  658.         bs_tree_search(bs_tree_test, rd_key, dlist_test);//相同key值的数据会被放入双向链表中
  659.         dlist_node = dlist_test->head;
  660.         for (j=0; j<dlist_test->len; j++)//相同key值的节点数据
  661.         {
  662.             memcpy(tree_node_read[j], dlist_node->value, 10);
  663.             dlist_node = dlist_node->next;
  664.         }
  665.         double_list_node_empty(dlist_test, 0);//清空双向链表节点
  666.     }
  667.     
  668.     /*中序遍历*/
  669.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);
  670.     dlist_node = dlist_test->head;
  671.     for (i=0; i<dlist_test->len; i++)
  672.     {
  673.         memcpy(tree_node_read[i], dlist_node->value, 10);
  674.         dlist_node = dlist_node->next;
  675.     }
  676.     double_list_node_empty(dlist_test, 0);
  677.  
  678.     
  679.     
  680.     
  681.     
  682.     /*删除 -- 查询*/
  683.     sprintf(del_key, "AAA%d", key[0]);
  684.     bs_tree_delete(bs_tree_test, del_key);
  685.     for (i=0; i<10; i++)
  686.     {
  687.         memset(tree_node_read[i], 0, 10);
  688.     }
  689.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);/*中序遍历*/
  690.     dlist_node = dlist_test->head;
  691.     for (i=0; i<dlist_test->len; i++)
  692.     {
  693.         memcpy(tree_node_read[i], dlist_node->value, 10);
  694.         dlist_node = dlist_node->next;
  695.     }
  696.     double_list_node_empty(dlist_test, 0);
  697.     /*删除 -- 查询*/
  698.     sprintf(del_key, "AAA%d", key[1]);
  699.     bs_tree_delete(bs_tree_test, del_key);
  700.     for (i=0; i<10; i++)
  701.     {
  702.         memset(tree_node_read[i], 0, 10);
  703.     }
  704.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);/*中序遍历*/
  705.     dlist_node = dlist_test->head;
  706.     for (i=0; i<dlist_test->len; i++)
  707.     {
  708.         memcpy(tree_node_read[i], dlist_node->value, 10);
  709.         dlist_node = dlist_node->next;
  710.     }
  711.     double_list_node_empty(dlist_test, 0);
  712.     /*删除 -- 查询*/
  713.     sprintf(del_key, "AAA%d", key[2]);
  714.     bs_tree_delete(bs_tree_test, del_key);
  715.     for (i=0; i<10; i++)
  716.     {
  717.         memset(tree_node_read[i], 0, 10);
  718.     }
  719.     bs_tree_inorder(bs_tree_test, bs_tree_test->root, dlist_test);/*中序遍历*/
  720.     dlist_node = dlist_test->head;
  721.     for (i=0; i<dlist_test->len; i++)
  722.     {
  723.         memcpy(tree_node_read[i], dlist_node->value, 10);
  724.         dlist_node = dlist_node->next;
  725.     }
  726.     double_list_node_empty(dlist_test, 0);
  727.     
  728.     
  729.     /*释放二叉树 和 双向链表结构*/
  730.     double_list_destroy(dlist_test, 0);
  731.     bs_tree_destroy(&bs_tree_test);
  732. }

4、调试问题

1、逻辑判断的运算符优先级要比赋值运算符优先级高

正确写法：while((del_node != NULL)&&((res = bstree->keycmp(bstree, key, del_node->key)) != 0))

错误写法：while ((del_node != NULL) && (res = bstree->keycmp(bstree, key, del_node->key) != 0))

2、指针变量传参时，如果要修改该指针变量的值即指针本身需要传入指针变量的地址，即使用双重指针才能。如本文中的 二叉树节点清空和二叉树销毁

 

六、说明

本文部分内容（图片与部分文字）为学习王争老师在极客时间专栏——《数据结构与算法之美》的学习总结。仅仅是个人学习备忘，如有侵犯权益，请联系我，立即修改。

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop博客】
推荐阅读
相关标签

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

  

闽ICP备14008679号