ITPub博客

首页 > 应用开发 > IT综合 > 二叉排序树查找,插入,删除

二叉排序树查找,插入,删除

原创 IT综合 作者:dongyu2013 时间:2014-04-11 16:31:54 0 删除 编辑

点击(此处)折叠或打开

  1. typedef struct BiTNode
  2. {
  3.     int data;
  4.     struct BiTNode *lchild, *rchild;
  5. }BiTNode, *BiTree;

  6. //递归查找二叉排序树T中是否存在key
  7. //指针f指向T的双亲,其初始化调用值为NULL
  8. //若查找成功,则指针p指向该数据元素节点,并返回TURE
  9. //否则指针p指向查找路径上访问的最后一个节点并返回FALSE
  10. bool SearchBST(BiTree T, int key, BiTree f, BiTree *p)
  11. {
  12.     if(!T)
  13.     {
  14.         *p=f;
  15.         return FALSE;
  16.     }
  17.     else if(key==T->data)
  18.     {
  19.      *p=T;
  20.         return TRUE;
  21.     }
  22.     else if(key<T->data)
  23.     {
  24.         return SearchBST(T->lchild, key, T, p);
  25.     }
  26.     else
  27.     {
  28.         return SearchBST(T->rchild, key, T, p);
  29.     }
  30. }

  31. //当二叉树排序树T中不存在关键字等于key的数据元素时
  32. //插入key并返回TRUE, 否则返回FALSE

  33. bool InsertBST(BiTree *T, int key)
  34. {
  35.     BiTree p,s;
  36.     if(!SearchBST(*T, key, NULL, &p))
  37.     {
  38.         s=(BiTree)malloc(sizeof(BiTNode));
  39.         s->data=key;
  40.         s->lchild=s->rchild=NULL;
  41.         if(!p)
  42.         {
  43.             *T=s;
  44.         }
  45.         else if(key<p->data)
  46.         {
  47.             p->lchild=s;
  48.         }
  49.         else
  50.         {
  51.             p->rchild=s;
  52.         }
  53.         return true;
  54.     }
  55.     else
  56.     {
  57.         return false;
  58.     }
  59. }


  60. bool Delete(BiTree *p)
  61. {
  62.     BiTree q,s;
  63.     if( (*p)->rchild==NULL )
  64.     {
  65.         q=*p; *p=(*p)->lchild; free(q);
  66.     }
  67.     else if( (*p)->lchild==NULL )
  68.     {
  69.         q=*p; *p=(*p)->rchild; free(q);
  70.     }
  71.     else
  72.     {
  73.         q=*p; s=(*p)->lchild;
  74.         while(s->rchild)
  75.         {
  76.             q=s; s=s->rchild;
  77.         }
  78.         (*p)->data=s->data;
  79.         if(q!=*p)
  80.             q->rchild=s->lchild;
  81.         else
  82.             q->lchild=s->rchild;
  83.     }
  84.     return true;
  85. }


  86. bool DeleteBST(BiTree *T, int key)
  87. {
  88.     if(!*T)
  89.     {
  90.         return false;
  91.     }
  92.     else
  93.     {
  94.         if(key==(*T)->data)
  95.         {
  96.             return Delete(T);
  97.         }
  98.         else if (key<(*T)->data)
  99.         {
  100.             return DeleteBST(&(*T)->lchild, key);
  101.         }
  102.         else
  103.         {
  104.             return DeleteBST(&(*T)->rchild, key);
  105.         }
  106.     }
  107. }

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/29012686/viewspace-1140292/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2013-12-25

  • 博文量
    263
  • 访问量
    209120