这个二叉树的结点的删除有什么问题,帮忙看看。谢谢

时间:2021-02-28 10:11:11
btree binary_search(btree point,int node)
{
   while(point!=NULL)
   {
      if(point->data==node)
         return point;
      else if(point->data>node)
         point=point->left;
      else
        point=point->right;
   }
 return NULL;
}
btree deletnode(btree root,int node)
{
   btree parent,point,child,position;
   parent=binary_search(point,node);
   point=parent;
   if(parent==NULL)
   return root;
   else
   {
     
      if(point->left==NULL&&point->right==NULL)
      {
         parent->left=NULL;
         parent->right=NULL;
         
      }
      else if(point->left==NULL&&point->right!=NULL)
      {
         if(parent!=point)
         parent->right=point->right;
         else
         root=root->right;
         free(point);
      }
      else if(point-left!=NULL&&point->right==NULL)
      {
         if(parent!=point)
         parent->left=point->left;
         else
         root=root->right;
         free(point);
      }
      else if(point->left!=NULL&&point->right!=NULL)
      {
          parent=point;
          child=point->left;
          while(child->right!=NULL)
          {
             parent=child;
             child=child->right;
          }
          point->data=child->data;
          if(parent->left==child)
          parent->left=child->left;
          else
          parent->right=child->right;
          free(child);
          return root;
      }
   }
}
我真的急死了,麻烦大哥大姐帮我看一下。万分感谢拉!!!

6 个解决方案

#1


point=parent;
...
if(point->left==NULL&&point->right==NULL)
      {
         parent->left=NULL;
         parent->right=NULL;
         
      }
//你这个语句没什么意思。没用。


关于二叉排序树的删除,数据结构的书上有很详细的代码,你可以看看。

#2


parent,point,你认为你的这两个变量在下面两句话中各自表达了自己的意思吗?
parent=binary_search(point,node);
point=parent;
很明显parent应该是父节点,point是当前节点,两个不应该相等。
而且,做二叉树一边参数传递都是用指针,你用的是指针吗?如果你的用的是对象
那么很可能出现内存泄漏或是拷贝构造问题。
此外你的btree binary_search(btree point,int node)函数真的能起作用吗?这个里面
连循环语句都没有,也没有用到递规调用。
还是自己好好看看数据结构的书吧,做什么事都是开头难,做多了也就容易了!

#3


下次弄点注释上来吧,根本不知道你的变量啥意思,你这样写的东西我估计很少有人有耐心看完。

#4


没有注释


看得很乱...

#5


btree deletnode(btree root,int node)  

node  应该就是要删除接点的值了



point=parent;

后面的

if(point->left==NULL&&point->right==NULL)
      {
         parent->left=NULL;
         parent->right=NULL;
         
      }

if(parent!=point)

都混乱拉!

算法不对了....



看你的程序 

你的parent 应该是point  的父接点才对

#6


删除节点有三种删除的方法了 要看你是用哪一种 给你看以前我做课程设计时候用的
void delbstnode(bstree *tptr,datatype key)
{
                                                    /*在二叉排序树*Tptr中删去关键字为key的结点*/
    bstnode *parent=NULL,*p=*tptr,*q,*child;
    while(p)
    {                                               /*从根开始查找关键字为key的待删结点*/
        if(p->key==key) break;                      /*已找到,跳出查找循环*/
        parent=p;                                   /*parent指向*p的双亲*/
        p=(key<p->key)?p->lchild:p->rchild;         /*在关p的左或右子树中继续找*/
}                                               
    if(!p) return;                                  /*找不到被删结点则返回*/
    q=p;                                            /*q记住被删结点*p*/
    if(q->lchild&&q->rchild)                        /* *q的两个孩子均非空,故找*q的中序后继*p  */
        for(parent=q,p=q->rchild;p->lchild;parent=p,p=p=->lchild);
                                                    /*现在情况(3)已被转换为情况(2),而情况(1)相当于是情况(2)中child=NULL的状况*/
            child=(p->lchild)?p->lchild:p->rchild;  /* 若是情况(2),则child非空;否则child为空  */
    if(!parent)                                     /* *p的双亲为空,说明*p为根,删*p后应修改根指针    */
        *tptr=child;                                /*若是情况(1),则删去*p后,树为空;否则child变为根    */
    else
    {                                               /*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下    */
        if(p==parent->lchild)                       /* *p是双亲的左孩子       */
            parent->lchild=child;                   /**child作为*parent的左孩子   */
        else parent->rchild=child;                  /* *child作为 parent的右孩子*/
        if(p!=q)                                    /*是情况(3),需将*p的数据复制到*q*/
            q->key=p->key;                          /*若还有其它数据域亦需复制  */
    }
    free(p);                                        /*释放*p占用的空间*/
}

#1


point=parent;
...
if(point->left==NULL&&point->right==NULL)
      {
         parent->left=NULL;
         parent->right=NULL;
         
      }
//你这个语句没什么意思。没用。


关于二叉排序树的删除,数据结构的书上有很详细的代码,你可以看看。

#2


parent,point,你认为你的这两个变量在下面两句话中各自表达了自己的意思吗?
parent=binary_search(point,node);
point=parent;
很明显parent应该是父节点,point是当前节点,两个不应该相等。
而且,做二叉树一边参数传递都是用指针,你用的是指针吗?如果你的用的是对象
那么很可能出现内存泄漏或是拷贝构造问题。
此外你的btree binary_search(btree point,int node)函数真的能起作用吗?这个里面
连循环语句都没有,也没有用到递规调用。
还是自己好好看看数据结构的书吧,做什么事都是开头难,做多了也就容易了!

#3


下次弄点注释上来吧,根本不知道你的变量啥意思,你这样写的东西我估计很少有人有耐心看完。

#4


没有注释


看得很乱...

#5


btree deletnode(btree root,int node)  

node  应该就是要删除接点的值了



point=parent;

后面的

if(point->left==NULL&&point->right==NULL)
      {
         parent->left=NULL;
         parent->right=NULL;
         
      }

if(parent!=point)

都混乱拉!

算法不对了....



看你的程序 

你的parent 应该是point  的父接点才对

#6


删除节点有三种删除的方法了 要看你是用哪一种 给你看以前我做课程设计时候用的
void delbstnode(bstree *tptr,datatype key)
{
                                                    /*在二叉排序树*Tptr中删去关键字为key的结点*/
    bstnode *parent=NULL,*p=*tptr,*q,*child;
    while(p)
    {                                               /*从根开始查找关键字为key的待删结点*/
        if(p->key==key) break;                      /*已找到,跳出查找循环*/
        parent=p;                                   /*parent指向*p的双亲*/
        p=(key<p->key)?p->lchild:p->rchild;         /*在关p的左或右子树中继续找*/
}                                               
    if(!p) return;                                  /*找不到被删结点则返回*/
    q=p;                                            /*q记住被删结点*p*/
    if(q->lchild&&q->rchild)                        /* *q的两个孩子均非空,故找*q的中序后继*p  */
        for(parent=q,p=q->rchild;p->lchild;parent=p,p=p=->lchild);
                                                    /*现在情况(3)已被转换为情况(2),而情况(1)相当于是情况(2)中child=NULL的状况*/
            child=(p->lchild)?p->lchild:p->rchild;  /* 若是情况(2),则child非空;否则child为空  */
    if(!parent)                                     /* *p的双亲为空,说明*p为根,删*p后应修改根指针    */
        *tptr=child;                                /*若是情况(1),则删去*p后,树为空;否则child变为根    */
    else
    {                                               /*p不是根,将*p的孩子和*p的双亲进行连接,*p从树上被摘下    */
        if(p==parent->lchild)                       /* *p是双亲的左孩子       */
            parent->lchild=child;                   /**child作为*parent的左孩子   */
        else parent->rchild=child;                  /* *child作为 parent的右孩子*/
        if(p!=q)                                    /*是情况(3),需将*p的数据复制到*q*/
            q->key=p->key;                          /*若还有其它数据域亦需复制  */
    }
    free(p);                                        /*释放*p占用的空间*/
}