首页 > 其他分享 >C语言数据结构之二叉树（BINARY TREE）链式存贮的简单实现

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

时间：2024-11-01 08:51:39浏览次数：3  
标签：node BINARY BTreeNode val TREE 二叉树 btree root append

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!!1
  btree_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);
  else
    printf ("Not found node val == 60\n");

  tmp = btree_search (root, 65);
  if (tmp != NULL)
    printf ("Found node : val ==> %d\n", tmp->val);
  else
    printf ("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; } //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_aappend_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, 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; } //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, 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!!1
  btree_prevorder_traversal (root); printf ("\n"); //OK!!1
  btree_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);
  else
    printf ("Not found node val == 60\n");

  tmp = btree_search (root, 65);
  if (tmp != NULL)
    printf ("Found node : val ==> %d\n", tmp->val);
  else
    printf ("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;
}
/* --[.^.]-- */
  • 下一步研究将这个树结构改造成可以存贮多种数据类型的数据结构！！！

标签：node,BINARY,BTreeNode,val,TREE,二叉树,btree,root,append
From： https://blog.csdn.net/gwsong52/article/details/143422551

相关文章

  • 二叉树专题学习
    前言：由于二叉树这一章的题型比较多，涉及到的递归程序也较多，所以单开一个随笔来记录这个学习过程，希望对读者有帮助。理论知识基础在二叉树的选择题中，常常会涉及到对于最多或最少结点、最大或最小高度、求叶子结点个数这几类经典的问题。上机题1.二叉树的建立和遍历P1305新二......
  • 108-二叉树-将有序数组转换为二叉搜索树
    树|二叉搜索树|数组|分治|二叉树二叉搜索树（BinarySearchTree,简称BST）和平衡二叉搜索树（BalancedBinarySearchTree）是计算机科学中非常重要的数据结构，广泛应用于各种算法和系统中。理解它们的定义、特点和性质对于掌握数据结构和算法至关重要。下面，我们将详细......
  • 有序二叉树简介
    有序二叉树有序二叉树：左边的结点值小于当前结点，右边结点值大于当前结点。有序二叉树结点模型root表示指向根结点的指针。构建有序二叉树判断root是否为nullroot为空，root=node如果root不为空，定义index游标，初始值==root。判断index和node结点值的大小二叉树的......
  • 【数据结构多彩画卷】不要只会普通的二叉树了 , 你听说过用二叉树来排序吗？ 【二叉搜索
    本篇会加入个人的所谓鱼式疯言❤️❤️❤️鱼式疯言:❤️❤️❤️此疯言非彼疯言而是理解过并总结出来通俗易懂的大白话,小编会尽可能的在每个概念后插入鱼式疯言,帮助大家理解的.......
  • 代码随想录算法训练营第十二天| 226.翻转二叉树、101. 对称二叉树、104.二叉树的最大
    226.翻转二叉树题目链接：.-力扣（LeetCode）文章讲解：代码随想录视频讲解：听说一位巨佬面Google被拒了，因为没写出翻转二叉树|LeetCode：226.翻转二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com......
  • 代码随想录算法训练营第十三天| 110.平衡二叉树、257. 二叉树的所有路径、404.左叶子
    110.平衡二叉树题目链接：.-力扣（LeetCode）文章链接：代码随想录视频链接：后序遍历求高度，高度判断是否平衡|LeetCode：110.平衡二叉树_哔哩哔哩_bilibili《代码随想录》算法公开课开讲啦！快来打卡！本期视频的文字讲解版在「代码随想录」刷题网站：programmercarl.com，这里刷题顺序，详......
  • 给定一个二叉树，找出其最大深度
      文心快码(BaiduComate)是基于百度文心大模型，在研发全流程全场景下为开发者提供辅助建议的智能代码助手。结合百度积累多年的编程现场大数据、外部优秀开源数据，可为开发者生成更符合实际研发场景的优秀代码，提升编码效率，释放“十倍”软件生产力。......
  • P 7-1 二叉树的遍历！（简单）
    二叉树作为FDS课程最核心的数据结构之一，要求每个人都掌握！这是一道简单的二叉树问题！我们将给出一颗二叉树，请你输出它的三种遍历，分别是先序遍历，中序遍历，后序遍历！输入格式:二叉树将以这样的形式给出：第一行给出一个正整数N（N<=100)，表示二叉树上的节点个数！接下来N行，每行包含三......
  • 代码随想录day14 二叉树（2）
    文章目录day11栈与队列(2)栈与队列的总结day13二叉树（1）day14二叉树（2）day11栈与队列(2)逆波兰表达式求值https://leetcode.cn/problems/evaluate-reverse-polish-notation/逆波兰表达式，也就是后缀表达式，所谓后缀就是指运算符写在后面。平常使用的算式则是一种......
  • Delphi10.3中的TreeView1的使用说明
    mySQL数据库中，所有的DataBase及其对应的Tables;最终效果： 先在设计窗口，新建根结点 再添加层级为Level1级的数据库名DataBases;varRootNode,DBNodes:TTreeNode;//先建立一个TREEVIEW使用的结点对象beginFDQuery1.Active:=false;FDQuery1.SQL.Text:='S......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99