当前位置： 首页 > news >正文

C语言数据结构之二叉树（BINARY TREE）链式存贮的简单实现

news 2024/11/1 10:06:32

C语言数据结构之二叉树（BINARY TREE）链式存贮的简单实现

  • 树型数据结构在应用中非常多，效率也非常好，只是结构相对复杂，理解起来有点儿难度！！！

定义数据结构

typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {int val;BTreeNode *lchild, *rchild;
};
  • 自定义结构体数据类型BTreeNode，成员包括val保存数据，lchild左子结点，rchild右子结点
  • 链式存贮，对编程来说更直观！！！
  • 为了便于测试，节点只保存整数！！！
  • 创建二叉树节点函数btree_node_new
  • 释放二叉树函数btree_free

代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>/* compile : gcc btree.c -o btree */
/*     run : ./btree              *//* define function pointer BTFunc for output */
typedef void (*BTFunc) (int val);/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {int val;BTreeNode *lchild, *rchild;
};/* create new BTreeNode */
BTreeNode *
btree_node_new (int val)
{BTreeNode *node = (BTreeNode*) malloc (sizeof(BTreeNode));node->val = val;node->lchild = NULL;node->rchild = NULL;return node;
}/* free a btree, every nodes in BTreeNode *root, recursion */
void
btree_free (BTreeNode *root)
{if (root != NULL){btree_free (root->lchild);btree_free (root->rchild);free (root);}
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *root = btree_node_new (100);btree_free (root);
}/**/
int
main (int argc, char *argv[])
{test_tree_append ();return 0;
}
/* --[.^.]-- */

编译运行，顺利通过，检测内存，达到预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
songvm@ubuntu:~/works/xdn/too$ valgrind --leak-check=yes ./btree
==3507== Memcheck, a memory error detector
==3507== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3507== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3507== Command: ./btree
==3507== 
==3507== 
==3507== HEAP SUMMARY:
==3507==     in use at exit: 0 bytes in 0 blocks
==3507==   total heap usage: 1 allocs, 1 frees, 24 bytes allocated
==3507== 
==3507== All heap blocks were freed -- no leaks are possible
==3507== 
==3507== For counts of detected and suppressed errors, rerun with: -v
==3507== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/too$

为树节点追加子节点，左侧追加append_left，右侧追加append_right，中序遍历inorder_traversal

  • 追加左子节点append_left，追加右子节点append_right
  • 中序遍历inorder_traversal 顺序为：左->根->右，用递归来实现！！！

代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>/* compile : gcc btree.c -o btree */
/*     run : ./btree              *//* define function pointer BTFunc for output */
typedef void (*BTFunc) (int val);/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {int val;BTreeNode *lchild, *rchild;
};/* create new BTreeNode */
BTreeNode *
btree_node_new (int val)
{BTreeNode *node = (BTreeNode*) malloc (sizeof(BTreeNode));node->val = val;node->lchild = NULL;node->rchild = NULL;return node;
}/* free a btree, every nodes in BTreeNode *root, recursion */
void
btree_free (BTreeNode *root)
{if (root != NULL){btree_free (root->lchild);btree_free (root->rchild);free (root);}
}/* append left child node to root with val */
void
btree_append_left (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->lchild = node;
}/* append right child node to root with val*/
void
btree_append_right (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->rchild = node;
}/* inorder traversal, left->root->right */
void
btree_inorder_traversal (BTreeNode *root)
{if (root != NULL){btree_inorder_traversal (root->lchild);printf ("%d ", root->val);btree_inorder_traversal (root->rchild);}
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *root = btree_node_new (50);btree_append_left (root, 40);btree_append_right (root, 60);btree_inorder_traversal (root);printf ("\n");btree_free (root);
}/**/
int
main (int argc, char *argv[])
{test_tree_append ();return 0;
}
/* --[.^.]-- */

编译运行，检测内存，效果如预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
40 50 60 
songvm@ubuntu:~/works/xdn/too$ valgrind --leak-check=yes ./btree
==3531== Memcheck, a memory error detector
==3531== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3531== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3531== Command: ./btree
==3531== 
40 50 60 
==3531== 
==3531== HEAP SUMMARY:
==3531==     in use at exit: 0 bytes in 0 blocks
==3531==   total heap usage: 4 allocs, 4 frees, 1,096 bytes allocated
==3531== 
==3531== All heap blocks were freed -- no leaks are possible
==3531== 
==3531== For counts of detected and suppressed errors, rerun with: -v
==3531== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/too$

实现了中序遍历，同理还可以实现前序遍历（根左右）和后序遍历（左右根）

  • 前序遍历prevorder_traversal，顺序：根->左->右
  • 后序遍历postorder_traversal，顺序：左->右->根
  • 另：追加未返回节点的指针，无法继续追加，需要改进！！！

代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>/* compile : gcc btree.c -o btree */
/*     run : ./btree              *//* define function pointer BTFunc for output */
typedef void (*BTFunc) (int val);/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {int val;BTreeNode *lchild, *rchild;
};/* create new BTreeNode */
BTreeNode *
btree_node_new (int val)
{BTreeNode *node = (BTreeNode*) malloc (sizeof(BTreeNode));node->val = val;node->lchild = NULL;node->rchild = NULL;return node;
}/* free a btree, every nodes in BTreeNode *root, recursion */
void
btree_free (BTreeNode *root)
{if (root != NULL){btree_free (root->lchild);btree_free (root->rchild);free (root);}
}/* append left child node to root with val */
BTreeNode*
btree_append_left (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->lchild = node;return node;
}/* append right child node to root with val*/
BTreeNode*
btree_append_right (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->rchild = node;return node;
}/* inorder traversal, left->root->right */
void
btree_inorder_traversal (BTreeNode *root)
{if (root != NULL){btree_inorder_traversal (root->lchild);printf ("%d ", root->val);btree_inorder_traversal (root->rchild);}
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (50);na = btree_append_left (root, 40);nb = btree_append_right (root, 60);btree_append_left (na, 20);btree_append_right (na, 30);btree_append_left (nb, 70);btree_append_right (nb, 80);btree_inorder_traversal (root);printf ("\n");btree_free (root);
}/**/
int
main (int argc, char *argv[])
{test_tree_append ();return 0;
}
/* --[.^.]-- */

编译运行，效果如预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
20 40 30 50 70 60 80 
songvm@ubuntu:~/works/xdn/too$ valgrind --leak-check=yes ./btree
==3541== Memcheck, a memory error detector
==3541== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==3541== Using Valgrind-3.13.0 and LibVEX; rerun with -h for copyright info
==3541== Command: ./btree
==3541== 
20 40 30 50 70 60 80 
==3541== 
==3541== HEAP SUMMARY:
==3541==     in use at exit: 0 bytes in 0 blocks
==3541==   total heap usage: 8 allocs, 8 frees, 1,192 bytes allocated
==3541== 
==3541== All heap blocks were freed -- no leaks are possible
==3541== 
==3541== For counts of detected and suppressed errors, rerun with: -v
==3541== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
songvm@ubuntu:~/works/xdn/too$

测试中序遍历、前序遍历和后序遍历，运行结果如下，达到预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
20 40 30 50 70 60 80 
50 20 40 30 70 60 80 
20 40 30 50 70 60 80 
songvm@ubuntu:~/works/xdn/too$

这种显示为一行对调试来说并不直观，可以更直观一些

  • 每行显示一个树节点，根据树的高度，循环输出空格，为函数传参数lv，初始值为0，每调用一次加1！！！
  • 为函数传参数lr，用字符R或L来标出是左还是右，根据R或L输出字符<或>！！！

代码如下：

/**/
void
btree_mid_print_lrv (BTreeNode *root, int lv, char lr)
{if (root != NULL){btree_mid_print_lrv (root->lchild, lv + 1, 'L');for (int i = 0; i < lv; i++) printf ("  ");if (lr == 'L') printf ("<");if (lr == 'R') printf (">");printf ("%d\n", root->val);btree_mid_print_lrv (root->rchild, lv + 1, 'R');}
}/**/
void
btree_mid_print (BTreeNode *root)
{btree_mid_print_lrv (root, 0, 'N');
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (50);na = btree_append_left (root, 40);nb = btree_append_right (root, 60);btree_append_left (na, 20);btree_append_right (na, 30);btree_append_left (nb, 70);btree_append_right (nb, 80);//btree_inorder_traversal (root); printf ("\n"); //OK!!1btree_mid_print (root);btree_free (root);
}

编译运行，达到预期，结果如下：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree<20<40>30
50<70>60>80
songvm@ubuntu:~/works/xdn/too$

上面显示的结果是不完整的，因为没有显示空节点！！！

  • 在函数：btree_mid_print_lrv中的if结构下面加上else，用#代表空节点！

代码如下：

  else{for (int i = 0; i < lv; i++) printf ("  ");if (lr == 'L') printf ("<");if (lr == 'R') printf (">");printf ("#\n");}

编译运行，效果如预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree<#<20>#<40<#>30>#
50<#<70>#>60<#>80>#
songvm@ubuntu:~/works/xdn/too$

二叉树的查找功能search

  • 按给定的值查找节点，btree_search函数

代码如下：

/* search val in BTreeNode root return node pointer */
BTreeNode *
btree_search (BTreeNode *root, int val)
{BTreeNode *node = NULL;if (root != NULL){if (root->val == val) return root;node = btree_search (root->lchild, val);if (node != NULL) return node;node = btree_search (root->rchild, val);}return node;
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *na, *nb, *root, *tmp;root = btree_node_new (50);na = btree_append_left (root, 40);nb = btree_append_right (root, 60);btree_append_left (na, 20);btree_append_right (na, 30);btree_append_left (nb, 70);btree_append_right (nb, 80);//btree_inorder_traversal (root); printf ("\n"); //OK!!1//btree_mid_print (root);tmp = btree_search (root, 60);if (tmp != NULL)printf ("Found node : val ==> %d\n", tmp->val);elseprintf ("Not found node val == 60\n");tmp = btree_search (root, 65);if (tmp != NULL)printf ("Found node : val ==> %d\n", tmp->val);elseprintf ("Not found node val == 65\n");btree_free (root);
}

编译运行，结果如预期（60存在故找到，65不存在故找不到）：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
Found node : val ==> 60
Not found node val == 65
songvm@ubuntu:~/works/xdn/too$

二叉树节点的删除remove

  • 按给定值删除节点，就复杂了，首先用上面的查找方法，找到节点！

  • 分以下几种情况：

  • 1、叶子节点，左右子节点均为空，直接删除！

  • 2、只有一个子节点的（左或右子节点），左右子节点有一个为空，删除后，子节点递补！

  • 3、有两个子节点，左右子节点均不为空，以右子节点为主，向上递补！

  • 4、根节点，有子节点，向上浮动值，删除最后一个子节点！

  • 5、根节点，无子节点，不删除，留给编程者自己释放！

  • 浮动调整函数 btree_adjust

  • 移动节点函数 btree_aappend_node_toleft，有两个字节点的树节点被删除后，左子节点附加到右子节点的左子节点上！

  • 删除节点同时指出该节点的父节点，是左子节点还是右子节点 btree_remove_bylr

  • 删除节点函数 btree_remove，全树查找值为val的节点，找到后删除！！！

代码如下：

/* adjust data of tree node and free not inuse tree node */
static void
btree_adjust (BTreeNode *root)
{char lr = 'N';BTreeNode *pn = root, *node;if (root->rchild != NULL) { node = root->rchild; lr = 'R'; }else if (root->lchild != NULL) { node = root->lchild; lr = 'L'; }else{ return; } //*root = NULL; return; } //todoroot->val = node->val;while (node->rchild != NULL){BTreeNode *tmp = node->rchild;pn = node;node->val = tmp->val;node = tmp;}if (lr == 'R') pn->rchild = NULL;if (lr == 'L') pn->lchild = NULL;free (node);
}/* append node tmp to node root */
static void
btree_aappend_node_toleft (BTreeNode *root, BTreeNode *tmp)
{if (root->lchild == NULL){ root->lchild = tmp; return; }else if (root->rchild == NULL){ root->rchild = tmp; return; }elsebtree_append_node_toleft (root->lchild, tmp);
}/* remove BTreeNode by val on node, call with parent node */
int
btree_remove_bylr (BTreeNode *node, BTreeNode *parent, char lr, int val)
{if (node != NULL){if (node->val == val){if (node->lchild == NULL && node->rchild == NULL){if (parent != NULL){if (lr == 'L') parent->lchild = NULL;if (lr == 'R') parent->rchild = NULL;free (node);}else{printf ("Remove the root node is a foolish operate!\n");}return 1;}else if (node->lchild == NULL){BTreeNode *tmp = node->rchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmp;if (lr == 'R') parent->rchild = tmp;free (node);}else{btree_adjust (node);}return 1;}else if (node->rchild == NULL){BTreeNode *tmp = node->lchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmp;if (lr == 'R') parent->rchild = tmp;free (node);}else{btree_adjust (node);}return 1;}else{BTreeNode *tmp = node;BTreeNode *tmpx = node->lchild;BTreeNode *tmpy = node->rchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmpy;if (lr == 'R') parent->rchild = tmpy;free (tmp);}else{btree_adjust (node);return 1;}btree_append_node_toleft (tmpy, tmpx);return 1;}}else{int ret;ret = btree_remove_bylr (node->lchild, node, 'L', val);if (ret == 0)ret = btree_remove_bylr (node->rchild, node, 'R', val);return ret;}}return 0;
}/* remove node by val in root if ok return 1 else return 0 */
int
btree_remove (BTreeNode *root, int val)
{return btree_remove_bylr (root, NULL, 'N', val);
}
  • 测试代码如下：
/**/
void
test_tree_remove_leaf (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 1);btree_remove (root, 2);btree_remove (root, 6);btree_remove (root, 8);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}

编译运行，效果如下，删除全部子节点，达到预期！！！

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree<#<1>#<3<#>2>#
5<#<6>#>7<#>8>#
--------------------<#<3>#
5<#>7>#
--------------------
songvm@ubuntu:~/works/xdn/too$

测试删除有两个子结点的结点

代码如下：

/**/
void
test_tree_remove_node (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 3);btree_remove (root, 7);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}

编译运行，结果如下，达到预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree<#<1>#<3<#>2>#
5<#<6>#>7<#>8>#
--------------------<#<1>#<2>#
5<#<6>#>8>#
--------------------
songvm@ubuntu:~/works/xdn/too$

测试删除有一个子节点的节点

代码如下：

/**/
void
test_tree_remove_node_mid (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 3);btree_remove (root, 7);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 2);btree_remove (root, 8);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}

编译运行，结果如下，达到预期：

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree<#<1>#<3<#>2>#
5<#<6>#>7<#>8>#
--------------------<#<1>#<2>#
5<#<6>#>8>#
--------------------<#<1>#
5<#>6>#
--------------------
songvm@ubuntu:~/works/xdn/too$
  • 个人认为删除根结点是愚蠢的，因为最后要释放掉，这会造成两次释放同一个指针的错误！！！

完整代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>/* compile : gcc btree.c -o btree */
/*     run : ./btree              *//* define function pointer BTFunc for output */
typedef void (*BTFunc) (int val);/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {int val;BTreeNode *lchild, *rchild;
};/* create new BTreeNode */
BTreeNode *
btree_node_new (int val)
{BTreeNode *node = (BTreeNode*) malloc (sizeof(BTreeNode));node->val = val;node->lchild = NULL;node->rchild = NULL;return node;
}/* free a btree, every nodes in BTreeNode *root, recursion */
void
btree_free (BTreeNode *root)
{if (root != NULL){btree_free (root->lchild);btree_free (root->rchild);free (root);}
}/* append left child node to root with val */
BTreeNode*
btree_append_left (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->lchild = node;return node;
}/* append right child node to root with val*/
BTreeNode*
btree_append_right (BTreeNode *root, int val)
{BTreeNode *node = btree_node_new (val);root->rchild = node;return node;
}/* inorder traversal, left->root->right */
void
btree_inorder_traversal (BTreeNode *root)
{if (root != NULL){btree_inorder_traversal (root->lchild);printf ("%d ", root->val);btree_inorder_traversal (root->rchild);}
}/* prev order traversal, root->left->right */
void
btree_prevorder_traversal (BTreeNode *root)
{if (root != NULL){printf ("%d ", root->val);btree_inorder_traversal (root->lchild);btree_inorder_traversal (root->rchild);}
}/* post order traversal, left->right->root */
void
btree_postorder_traversal (BTreeNode *root)
{if (root != NULL){btree_inorder_traversal (root->lchild);printf ("%d ", root->val);btree_inorder_traversal (root->rchild);}
}/**/
void
btree_mid_print_lrv (BTreeNode *root, int lv, char lr)
{if (root != NULL){btree_mid_print_lrv (root->lchild, lv + 1, 'L');for (int i = 0; i < lv; i++) printf ("  ");if (lr == 'L') printf ("<");if (lr == 'R') printf (">");printf ("%d\n", root->val);btree_mid_print_lrv (root->rchild, lv + 1, 'R');}else{for (int i = 0; i < lv; i++) printf ("  ");if (lr == 'L') printf ("<");if (lr == 'R') printf (">");printf ("#\n");}
}/**/
void
btree_mid_print (BTreeNode *root)
{btree_mid_print_lrv (root, 0, 'N');
}/* search val in BTreeNode root return node pointer */
BTreeNode *
btree_search (BTreeNode *root, int val)
{BTreeNode *node = NULL;if (root != NULL){if (root->val == val) return root;node = btree_search (root->lchild, val);if (node != NULL) return node;node = btree_search (root->rchild, val);}return node;
}/* adjust data of tree node and free not inuse tree node */
static void
btree_adjust (BTreeNode *root)
{char lr = 'N';BTreeNode *pn = root, *node;if (root->rchild != NULL) { node = root->rchild; lr = 'R'; }else if (root->lchild != NULL) { node = root->lchild; lr = 'L'; }else{ return; } //*root = NULL; return; } //todoroot->val = node->val;while (node->rchild != NULL){BTreeNode *tmp = node->rchild;pn = node;node->val = tmp->val;node = tmp;}if (lr == 'R') pn->rchild = NULL;if (lr == 'L') pn->lchild = NULL;free (node);
}/* append node tmp to node root */
static void
btree_append_node_toleft (BTreeNode *root, BTreeNode *tmp)
{if (root->lchild == NULL){ root->lchild = tmp; return; }else if (root->rchild == NULL){ root->rchild = tmp; return; }elsebtree_append_node_toleft (root->lchild, tmp);
}/* remove BTreeNode by val on node, call with parent node */
int
btree_remove_bylr (BTreeNode *node, BTreeNode *parent, char lr, int val)
{if (node != NULL){if (node->val == val){if (node->lchild == NULL && node->rchild == NULL){if (parent != NULL){if (lr == 'L') parent->lchild = NULL;if (lr == 'R') parent->rchild = NULL;free (node);}else{printf ("Remove the root node is a foolish operate!\n");}return 1;}else if (node->lchild == NULL){BTreeNode *tmp = node->rchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmp;if (lr == 'R') parent->rchild = tmp;free (node);}else{btree_adjust (node);}return 1;}else if (node->rchild == NULL){BTreeNode *tmp = node->lchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmp;if (lr == 'R') parent->rchild = tmp;free (node);}else{btree_adjust (node);}return 1;}else{BTreeNode *tmp = node;BTreeNode *tmpx = node->lchild;BTreeNode *tmpy = node->rchild;if (parent != NULL){if (lr == 'L') parent->lchild = tmpy;if (lr == 'R') parent->rchild = tmpy;free (tmp);}else{btree_adjust (node);return 1;}btree_append_node_toleft (tmpy, tmpx);return 1;}}else{int ret;ret = btree_remove_bylr (node->lchild, node, 'L', val);if (ret == 0)ret = btree_remove_bylr (node->rchild, node, 'R', val);return ret;}}return 0;
}/* remove node by val in root if ok return 1 else return 0 */
int
btree_remove (BTreeNode *root, int val)
{return btree_remove_bylr (root, NULL, 'N', val);
}/********************************//**/
void
test_tree_append (void)
{BTreeNode *na, *nb, *root, *tmp;root = btree_node_new (50);na = btree_append_left (root, 40);nb = btree_append_right (root, 60);btree_append_left (na, 20);btree_append_right (na, 30);btree_append_left (nb, 70);btree_append_right (nb, 80);btree_inorder_traversal (root); printf ("\n"); //OK!!1btree_prevorder_traversal (root); printf ("\n"); //OK!!1btree_postorder_traversal (root); printf ("\n"); //OK!!1//btree_mid_print (root);/*tmp = btree_search (root, 60);if (tmp != NULL)printf ("Found node : val ==> %d\n", tmp->val);elseprintf ("Not found node val == 60\n");tmp = btree_search (root, 65);if (tmp != NULL)printf ("Found node : val ==> %d\n", tmp->val);elseprintf ("Not found node val == 65\n");*/btree_free (root);
}/**/
void
test_tree_remove_leaf (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 1);btree_remove (root, 2);btree_remove (root, 6);btree_remove (root, 8);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}/**/
void
test_tree_remove_node (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 3);btree_remove (root, 7);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}/**/
void
test_tree_remove_node_mid (void)
{BTreeNode *na, *nb, *root;root = btree_node_new (5);na = btree_append_left (root, 3);nb = btree_append_right (root, 7);btree_append_left (na, 1);btree_append_right (na, 2);btree_append_left (nb, 6);btree_append_right (nb, 8);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 3);btree_remove (root, 7);btree_mid_print (root);printf ("--------------------\n");btree_remove (root, 2);btree_remove (root, 8);btree_mid_print (root);printf ("--------------------\n");btree_free (root);
}/**/
int
main (int argc, char *argv[])
{test_tree_append ();//test_tree_remove_leaf ();//test_tree_remove_node ();//test_tree_remove_node_mid ();return 0;
}
/* --[.^.]-- */
  • 下一步研究将这个树结构改造成可以存贮多种数据类型的数据结构！！！

http://www.mrgr.cn/news/63097.html

相关文章：

  • 【第一个qt项目的实现和介绍以及程序分析】【正点原子】嵌入式Qt5 C++开发视频
  • 传奇架设好后创建不了行会，开区时点创建行会没反应的解决办法
  • rom定制系列------红米note8_miui14安卓13定制修改固件 带面具root权限 刷写以及界面预览
  • 爬虫设计思路
  • 偷懒总结篇|贪心算法|动态规划|单调栈|图论
  • 无人机之目标检测算法篇
  • 猫头虎分享：Claude AI、ChatGPT 和 知乎直答的 AI 搜索大战
  • 深入探索C语言：fread函数的高效文件读取艺术
  • 2023-2024年教育教学改革、教学成果奖等项目申请书合集-最新出炉 附下载链接
  • 【如何获取股票数据31】Python、Java等多种主流语言实例演示获取股票行情api接口之沪深A股融资融券标的股数据获取实例演示及接口API说明文档
  • 2024年10月31日Day1
  • 基于Python的自然语言处理系列（50）：Soft Prompt 实现
  • IEC104规约的秘密之十九----6号文中的一些问题
  • IDEA修改生成jar包名字的两种方法实现
  • 前端八股文第八篇
  • Vue v-on 简写 @， v-bind 简写 ：
  • Vue v-html v-once v-if
  • 定制化视频生成新模范！零样本主体驱动，精确运动控制！复旦阿里等发布DreamVideo-2
  • 消息队列面试——打破沙锅问到底
  • 2024最新IntelliJ IDEA常用的小技巧汇总，JAVA 新手上路必备
  • 【Oracle APEX开发小技巧10】CSS样式控制交互式报表列宽和自动换行效果
  • Nginx 实现动态封禁IP，详细教程来了
  • 详细分析Vue3中的provide和inject基本知识（附Demo）
  • 华为OD机试 - 字符串消除 - 栈Stack（Python/JS/C/C++ 2024 C卷 100分）
  • 【Rust标准库中的convert（AsRef，From，Into，TryFrom，TryInto）】
  • wordpress argon主题美化方面