首页 > 其他分享 >C语言数据结构之二叉树（BINARY TREE）的多种数据类型存贮

C语言数据结构之二叉树（BINARY TREE）的多种数据类型存贮

时间：2024-11-09 12:44:06浏览次数：3  
标签：node BINARY BTreeNode val 数据类型 二叉树 btree root append

C语言数据结构之二叉树（BINARY TREE）的多种数据类型存贮

用无类型指针（void*）来做为基本数据类型来存贮数据，将其他数据类型强制转化为无类型指针，从而达到目标！！！

  • 输出函数指针 BTFunc
  • 比较函数指针 BTCmpFunc 返回值为整型值1、-1、0，表示大于、小于、相等

代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* compile : gcc btree.c -o btree */
/*     run : ./btree              */

/* define function pointer BTFunc for output */
typedef void (*BTFunc) (void *val);
typedef int  (*BTCmpFunc) (void *va, void *vb);

/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {
  void *val;
  BTreeNode *lchild, *rchild;
};

/* create new BTreeNode */
BTreeNode *
btree_node_new (void *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, void *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, void *val)
{
  BTreeNode *node = btree_node_new (val);
  root->rchild = node;
  return node;
}

/* inorder traversal, left->root->right */
void
btree_inorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btree_inorder_traversal (root->lchild, btfunc);
      btfunc (root->val);
      btree_inorder_traversal (root->rchild, btfunc);
    }
}

/* prev order traversal, left->root->right */
void
btree_prevorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btfunc (root->val);
      btree_inorder_traversal (root->lchild, btfunc);
      btree_inorder_traversal (root->rchild, btfunc);
    }
}

/* post order traversal, left->root->right */
void
btree_postorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btree_inorder_traversal (root->lchild, btfunc);
      btree_inorder_traversal (root->rchild, btfunc);
      btfunc (root->val);
    }
}

/*------------------------------*/
/**/
void
out_string (void *val)
{
  printf ("%s ", (char*)val);
}

/**/
void
out_string_newline (void *val)
{
  printf ("%s\n", (char*)val);
}

/**/
int
cmp_string (void *va, void *vb)
{
  return strcmp (va, vb);
}

/**/
void
test_tree_append (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;
  root = btree_node_new (buff[0]);

  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);

  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);

  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_inorder_traversal (root, out_string);   printf ("\n");
  btree_prevorder_traversal (root, out_string); printf ("\n");
  btree_postorder_traversal (root, out_string); printf ("\n");

  btree_free (root);
}

/**/
int
main (int argc, char *argv[])
{
  test_tree_append ();
  return 0;
}
/* --[.^.]-- */

编译运行，结果如下：

  • 字符串追加测试函数 test_tree_append
songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
DDD BBB EEE AAA FFF CCC GGG 
AAA DDD BBB EEE FFF CCC GGG 
DDD BBB EEE FFF CCC GGG AAA 
songvm@ubuntu:~/works/xdn/too$

更直观的显示树的结构

  • 二叉树中序遍历直观显示函数 btree_mid_print
  • btree_mid_print_lrv 参数lv表示层数每层加一，参数lr表示左右子节点，递归调用！！！
  • btree_mid_print 调用btree_mid_print_lrv，lv初始为0，lr初始为N，表示根（非左非右）

代码如下：

/* middle print tree node with btfunc by lv and lr */
static void
btree_mid_print_lrv (BTreeNode *root, BTFunc btfunc, int lv, char lr)
{
  if (root != NULL)
    {
      btree_mid_print_lrv (root->lchild, btfunc, lv + 1, 'L');
      for (int i = 0; i < lv; i++) printf ("  ");
      if (lr == 'L') printf ("<");
      if (lr == 'R') printf (">");
      btfunc (root->val);
      btree_mid_print_lrv (root->rchild, btfunc, lv + 1, 'R');
    }
  else
    {
      for (int i = 0; i < lv; i++) printf ("  ");
      if (lr == 'L') printf ("<");
      if (lr == 'R') printf (">");
      printf ("#\n");
    }
}

/* middle print tree node call btfunc */
void
btree_mid_print (BTreeNode *root, BTFunc btfunc)
{
  btree_mid_print_lrv (root, btfunc, 0, 'N');
}
  • 在test_tree_append函数代码下面加入函数调用：
  btree_mid_print (root, out_string_newline);

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

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
      <#
    <DDD
      >#
  <BBB
      <#
    >EEE
      >#
AAA
      <#
    <FFF
      >#
  >CCC
      <#
    >GGG
      >#
songvm@ubuntu:~/works/xdn/too$

按值（字符串）查找树节点

  • btree_search 函数，第三个参数为函数指针BTCmpFunc！！！

代码如下：

/* search val in BTreeNode root return node pointer call with btcmpfunc */
BTreeNode *
btree_search (BTreeNode *root, void *val, BTCmpFunc btcmpfunc)
{
  BTreeNode *node = NULL;
  if (root != NULL)
    {
      if (0 == btcmpfunc (root->val, val)) return root;
      node = btree_search (root->lchild, val, btcmpfunc);
      if (node != NULL) return node;
      node = btree_search (root->rchild, val, btcmpfunc);
    }
  return node;
}
  • 测试函数test_tree_append中加入代码：
  tmp = btree_search (root, "GGG", cmp_string);
  if (tmp != NULL)
    printf ("Found node : val ==> [%s]\n", (char*)(tmp->val));
  else
    printf ("Not found node val == [GGG]\n");

  tmp = btree_search (root, "HHH", cmp_string);
  if (tmp != NULL)
    printf ("Found node : val ==> [%s]\n", (char*)(tmp->val));
  else
    printf ("Not found node val == [HHH]\n");

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

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
Found node : val ==> [GGG]
Not found node val == [HHH]
songvm@ubuntu:~/works/xdn/too$

按值（字符串）删除结点

  • 删除节点 btree_remove 用到下面三个函数
  • 删除节点指定左右子节点和父节点 btree_remove_bylr 函数，递归调用！！！
  • btree_adjust
  • btree_append_node_toleft

代码如下：

/* 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; } //todo
  root->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; }
  else
    btree_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, void *val, BTCmpFunc btcmpfunc)
{
  if (node != NULL)
    {
      if (0 == btcmpfunc (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, btcmpfunc);
	  if (ret == 0)
	    ret = btree_remove_bylr (node->rchild, node, 'R', val, btcmpfunc);
	  return ret;
	}
    }
  return 0;
}

/* remove node by val in root if ok return 1 else return 0 */
int
btree_remove (BTreeNode *root, void *val, BTCmpFunc btcmpfunc)
{
  return btree_remove_bylr (root, NULL, 'N', val, btcmpfunc);
}

按值（字符串）删除叶节点

  • 测试函数 test_tree_remove_leaf

代码如下：

/* test remove leaf node function */
void
test_tree_remove_leaf (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "DDD", cmp_string);
  btree_remove (root, "EEE", cmp_string);
  btree_remove (root, "FFF", cmp_string);
  btree_remove (root, "GGG", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_free (root);
}

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

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
      <#
    <DDD
      >#
  <BBB
      <#
    >EEE
      >#
AAA
      <#
    <FFF
      >#
  >CCC
      <#
    >GGG
      >#
--------------------
    <#
  <BBB
    >#
AAA
    <#
  >CCC
    >#
--------------------
songvm@ubuntu:~/works/xdn/too$

检测内存分配释放情况，没问题！运行结果如下：

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

按值（字符串）删除中间节点（有两个子节点的节点）

  • 测试函数 test_tree_remove_node

代码如下：

/* test remove node with child node function */
void
test_tree_remove_node (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "BBB", cmp_string);
  btree_remove (root, "CCC", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_free (root);
}

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

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
      <#
    <DDD
      >#
  <BBB
      <#
    >EEE
      >#
AAA
      <#
    <FFF
      >#
  >CCC
      <#
    >GGG
      >#
--------------------
      <#
    <DDD
      >#
  <EEE
    >#
AAA
      <#
    <FFF
      >#
  >GGG
    >#
--------------------
songvm@ubuntu:~/works/xdn/too$

按值（字符串）删除有一个子节点的节点

  • 测试函数 test_tree_remove_node_mid

代码如下：

/* test remove node with one child node function */
void
test_tree_remove_node_mid (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "BBB", cmp_string);
  btree_remove (root, "CCC", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "GGG", cmp_string);
  btree_remove (root, "EEE", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_free (root);
}

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

songvm@ubuntu:~/works/xdn/too$ gcc btree.c -o btree
songvm@ubuntu:~/works/xdn/too$ ./btree
      <#
    <DDD
      >#
  <BBB
      <#
    >EEE
      >#
AAA
      <#
    <FFF
      >#
  >CCC
      <#
    >GGG
      >#
--------------------
      <#
    <DDD
      >#
  <EEE
    >#
AAA
      <#
    <FFF
      >#
  >GGG
    >#
--------------------
    <#
  <DDD
    >#
AAA
    <#
  >FFF
    >#
--------------------
songvm@ubuntu:~/works/xdn/too$

完整代码如下：

/* filename: btree.c */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* compile : gcc btree.c -o btree */
/*     run : ./btree              */

/* define function pointer BTFunc for output */
typedef void (*BTFunc) (void *val);
typedef int  (*BTCmpFunc) (void *va, void *vb);

/* define the BTreeNode datatype */
typedef struct _BTreeNode BTreeNode;
struct _BTreeNode {
  void *val;
  BTreeNode *lchild, *rchild;
};

/* create new BTreeNode */
BTreeNode *
btree_node_new (void *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, void *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, void *val)
{
  BTreeNode *node = btree_node_new (val);
  root->rchild = node;
  return node;
}

/* inorder traversal, left->root->right */
void
btree_inorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btree_inorder_traversal (root->lchild, btfunc);
      btfunc (root->val);
      btree_inorder_traversal (root->rchild, btfunc);
    }
}

/* prev order traversal, left->root->right */
void
btree_prevorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btfunc (root->val);
      btree_inorder_traversal (root->lchild, btfunc);
      btree_inorder_traversal (root->rchild, btfunc);
    }
}

/* post order traversal, left->root->right */
void
btree_postorder_traversal (BTreeNode *root, BTFunc btfunc)
{
  if (root != NULL)
    {
      btree_inorder_traversal (root->lchild, btfunc);
      btree_inorder_traversal (root->rchild, btfunc);
      btfunc (root->val);
    }
}

/* middle print tree node with btfunc by lv and lr */
static void
btree_mid_print_lrv (BTreeNode *root, BTFunc btfunc, int lv, char lr)
{
  if (root != NULL)
    {
      btree_mid_print_lrv (root->lchild, btfunc, lv + 1, 'L');
      for (int i = 0; i < lv; i++) printf ("  ");
      if (lr == 'L') printf ("<");
      if (lr == 'R') printf (">");
      btfunc (root->val);
      btree_mid_print_lrv (root->rchild, btfunc, lv + 1, 'R');
    }
  else
    {
      for (int i = 0; i < lv; i++) printf ("  ");
      if (lr == 'L') printf ("<");
      if (lr == 'R') printf (">");
      printf ("#\n");
    }
}

/* middle print tree node call btfunc */
void
btree_mid_print (BTreeNode *root, BTFunc btfunc)
{
  btree_mid_print_lrv (root, btfunc, 0, 'N');
}

/* search val in BTreeNode root return node pointer call with btcmpfunc */
BTreeNode *
btree_search (BTreeNode *root, void *val, BTCmpFunc btcmpfunc)
{
  BTreeNode *node = NULL;
  if (root != NULL)
    {
      if (0 == btcmpfunc (root->val, val)) return root;
      node = btree_search (root->lchild, val, btcmpfunc);
      if (node != NULL) return node;
      node = btree_search (root->rchild, val, btcmpfunc);
    }
  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; } //todo
  root->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; }
  else
    btree_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, void *val, BTCmpFunc btcmpfunc)
{
  if (node != NULL)
    {
      if (0 == btcmpfunc (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, btcmpfunc);
	  if (ret == 0)
	    ret = btree_remove_bylr (node->rchild, node, 'R', val, btcmpfunc);
	  return ret;
	}
    }
  return 0;
}

/* remove node by val in root if ok return 1 else return 0 */
int
btree_remove (BTreeNode *root, void *val, BTCmpFunc btcmpfunc)
{
  return btree_remove_bylr (root, NULL, 'N', val, btcmpfunc);
}

/*------------------------------*/

/**/
void
out_string (void *val)
{
  printf ("%s ", (char*)val);
}

/**/
void
out_string_newline (void *val)
{
  printf ("%s\n", (char*)val);
}

/**/
int
cmp_string (void *va, void *vb)
{
  return strcmp (va, vb);
}

/**/
void
test_tree_append (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;
  root = btree_node_new (buff[0]);

  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);

  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);

  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  //btree_inorder_traversal (root, out_string);   printf ("\n");
  //btree_prevorder_traversal (root, out_string); printf ("\n");
  //btree_postorder_traversal (root, out_string); printf ("\n");
  //btree_mid_print (root, out_string_newline);

  tmp = btree_search (root, "GGG", cmp_string);
  if (tmp != NULL)
    printf ("Found node : val ==> [%s]\n", (char*)(tmp->val));
  else
    printf ("Not found node val == [GGG]\n");

  tmp = btree_search (root, "HHH", cmp_string);
  if (tmp != NULL)
    printf ("Found node : val ==> [%s]\n", (char*)(tmp->val));
  else
    printf ("Not found node val == [HHH]\n");

  btree_free (root);
}

/* test remove leaf node function */
void
test_tree_remove_leaf (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "DDD", cmp_string);
  btree_remove (root, "EEE", cmp_string);
  btree_remove (root, "FFF", cmp_string);
  btree_remove (root, "GGG", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_free (root);
}

/* test remove node with child node function */
void
test_tree_remove_node (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "BBB", cmp_string);
  btree_remove (root, "CCC", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_free (root);
}

/* test remove node with one child node function */
void
test_tree_remove_node_mid (void)
{
  char *buff[7] = { "AAA", "BBB", "CCC", "DDD", "EEE", "FFF", "GGG"};
  BTreeNode *na, *nb, *root, *tmp;

  root = btree_node_new (buff[0]);
  na = btree_append_left (root, buff[1]);
  nb = btree_append_right (root, buff[2]);
  btree_append_left (na, buff[3]);
  btree_append_right (na, buff[4]);
  btree_append_left (nb, buff[5]);
  btree_append_right (nb, buff[6]);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "BBB", cmp_string);
  btree_remove (root, "CCC", cmp_string);

  btree_mid_print (root, out_string_newline);
  printf ("--------------------\n");

  btree_remove (root, "GGG", cmp_string);
  btree_remove (root, "EEE", cmp_string);

  btree_mid_print (root, out_string_newline);
  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;
}
/* --[.^.]-- */

下一步研究平衡二叉树！！！

标签：node,BINARY,BTreeNode,val,数据类型,二叉树,btree,root,append
From： https://blog.csdn.net/gwsong52/article/details/143476009

相关文章

  • 二叉树常用代码合集【C++版】（详细注释）
    二叉树常用代码合集【C++版】（详细注释）关键的地方有详细的注释。如果需要更详细的注释，可以丢给大模型再注释一遍。#include<iostream>#include<memory>#include<string>#definemv(x)std::move(x)#definecoutln(x)cout<<x<<endlusingnamespacestd;......
  • C++算法练习-day38——106.从中序和后序遍历序列构造二叉树
    题目来源：.-力扣（LeetCode）题目思路分析题目要求根据一棵二叉树的中序遍历（inorder）和后序遍历（postorder）结果重建这棵二叉树。中序遍历的特点是左子树->根节点->右子树，而后序遍历的特点是左子树->右子树->根节点。利用这两个遍历的特点，我们可以递归地重建整棵树。后序......
  • 7-8 数据结构实验二 二叉树的遍历
    以二叉链表作存储结构，建立一棵二叉树。输出该二叉树的先序、中序、后序遍历序列，求出该二叉树的深度，并统计其叶子结点数。二叉链表的类型描述：typedefcharElemType;typedefstructBiNode{ElemTypedata;structBiNode*lchild,*rchild;}BiNode,*BiTree;......
  • JS数据结构之树和二叉树
    一、树树（Tree）是一种非常常见的数据结构，它模拟了自然界中树的结构，由节点（或称为顶点）组成，并且具有层次化的组织形式。树结构在计算机科学中广泛应用，例如在组织数据、管理信息层次以及算法设计中。1.基本概念节点（Node）根节点（Root）：树的最顶端节点，没有父节点。内部节点（InternalNod......
  • Leecode热题100-104.二叉树中的最大路径和
    二叉树中的 路径 被定义为一条节点序列，序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点，且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ，返回其 最大路径和 。示例......
  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接：https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接：https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内，所以递归是要统计子树的高度的intg......
  • 二叉树遍历
    二叉树遍历这个问题，以前一直没搞懂，只是模糊的了解。先序遍历:先访问根节点，再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点，再访问根节点，最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树，再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
  • 二叉树 （王道数据结构 C语言版）
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归，都按照这三要素来写，可以保证大家写出正确的递归算法！确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件：写完了递归算法,运行的时......
  • python基础——04数据类型（元组，集合，字典）
    一、元组(tuple)1.1什么是元组元组和列表相似，但元组的元素放在()里面。t=(1,2,3,4,5)print(type(t))#<class'tuple'>t1=('hello')#<class'str'>这不是元组t2=('hello',)#<class'tuple'>print(type(t1),type(t2)......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99