请教一个查找二叉树结点删除的问题。

自学数据结构中，困难重重。。。。。。

请教一下各位高手，如下类型的一棵二叉查找树：
               80
             /    \
         40        100
       /    \
     20    50
           /
         10
如果删除50这个结点，这棵树会变成什么样？删除50时不连同它的叶子10一起删掉。

数据结构的书太难看了，而且我看的书（严蔚敏，清华）里面好像只是一个劲的讲查找，遍历，没讲删除结点的问题。
另外如果100那个结点有叶子，那么如果删除80这个根结点可以不？如果可以，这棵树又会变成什么样？

谢谢各位来看这个问题。

12 个解决方案

#1

你想让它的节点保留，还是删除掉，取决于你自己当时写数据结构的实际用途啊

数据结构这个板块高手太多了，写的程序很多都看不太懂阿

#2

谢谢你的回答，虽然作用不大。
我在CSDN其它版块，以及其它的专业的编程论坛上都问过这个问题，看都没人看别说解答了。
还是继续看那本难懂的书吧。

#3

这个简单的问题还是参考我回答好了
删除50后 50后面的节点归到它上面的节点去重新构造一个新的2叉查找书
具体可以参照西电出的考研数据结构这个是经常考的而且例题很多（假如我没记错出版社，最后一次看是3年前）
这版高手很多一般解决高难度算法问题看了个问题从C++ 讨论到汇编又讨论到电路图又给了篇国外的论文
慢慢看吧祝好运！

#4

你的问题出在你给的根本不是查找树，10是20的左子树怎么跑到50的左子树了？建立的时候就不是查找树怎么保证删除后是查找树？

#5

(1)如楼上所说，该树不是一个二叉查找树。二叉查找树的修改操作关键是保持二叉查找树的性质。
（２）如果要删除一个节点要分３种情况：１：叶子结点２：有一个孩子的节点３：有两个孩子的节点。情况１：叶子结点直接删除就可以了。情况２：删除该结点，将该节点的孩子结点连接到父结点上。情况３：实际要删除的节点是带删除结点的后继结点。所以可以先将后继结点替换掉待删除的节点，然后删除掉后继结点。
至于后继结点的算法，是一个子过程。
具体可以看：Introduction to Algorithms第３部分

#6

推荐看看北航唐发根写的 <<数据结构>>

#7

严蔚敏老师的数据结构对二叉查找树的插入删除等操作讲得很清楚阿

#8

同意楼上。入门了就好了

#9

大概是高手认为太简单了，所以没有人回答吧。
你的树，本身就有问题。

说下，删除的规则。

如果不是叶子节点，所以可以将当前要删除的节点50，那么必须找到一个在
以50为根节点的二叉树相邻的点来替换这个50的节点，显然排序后50有2个相邻的
，前一个（对应二叉树中的左子树中的最大（右）叶节点），后一个（右子树中最小（左）节点。

随片选择1个设为p，把他们交换就后，然后递归删除这个p节点，主意：这里一定要递归删除这个p。



DeleteNode(BTree* T)

{

 if( T is leafNode) delete;

//find A neighbourhood


//在左子树中，向右走到头 

p = T->left;

pre = p;

while(p)

{

 p=p->right;

}


if(pre!=p)

{

T->node = p->node;

DeleteNode(p);

return;

}


//左子树是空的，从右子树中找个点


p = T->right;

while(p)

{

p=p->left;

}


T->node = p->node;

DeleteNode(p);


}

#10

好久没来了，已经有这么多高手来了，谢谢。

我穷鬼一个，知识穷，分也穷，没分给各位真不好意。

唉，书看少了，以后要加强。

#11

正常结贴的按钮在哪里去了。怎么只有无满意结贴的按钮》

#12

void DeleteNode(node *n)
{     node* temp = n;
if(n!=NULL)
{        printf("deleting %d\n",n->data);
if (n->leftchild == NULL && n->rightchild!=NULL)
{           nn = n->rightchild;
delete temp;        }
if (n->rightchild == NULL && n->leftchild!=NULL)
{           nn = n->leftchild;
delete temp;        }
else
{           // 结点有两个孩子--得到最大的左子树
temp = n->leftchild;
  while (temp->rightchild != NULL)
{              temptemp = temp->rightchild;
   }
n->data = temp->data;DeleteNode(temp);
http://book.51cto.com/art/201008/220472.htm //这里有点代码也许有用 }
  }
else
return;  }

#1