请问如何正确删除二叉树中的某一结点,我下面写的哪里错了,该怎么改呢?
//删除树中的某一节点
template<typename T>
void __fastcall TMyBTree<T>::DeleteBT(TNode<T>* src,TNode<T>* par)
{
//TODO: Add your source code here
//src代表所要删除的结点,par表示src的父结点
TNode<T>* pTmp; // 保存当前节点
TNode<T>* pTmp2; // 保存当前节点的父节点
//TNode<T>* pTmp3; // 保存当前节点的右子节点
if(NULL == src->lChild && NULL == src->rChild) //此结点为叶子
{
if(m_pRoot == src) //表示src为根节点
m_pRoot = NULL;
else if(par->lChild == src) //为父节点的左子树
par->lChild = NULL;
else //为父节点的右子树
par->rChild = NULL;
SAFEDEL(src);
}
else if(NULL == src->lChild) //只有右子树
{
if(m_pRoot == src) //表示src为根节点
m_pRoot = src->rChild;
else if(par->lChild == src) //为父节点的左子树
par->lChild = src->rChild;
else //为父节点的右子树
par->rChild = src->rChild;
SAFEDEL(src);
}
else if(NULL == src->rChild) //只有左子树
{
if(m_pRoot == src) //表示src为根节点
m_pRoot = src->lChild;
else if(par->lChild == src) //为父节点的左子树
par->lChild = src->lChild;
else //为父节点的右子树
par->rChild = src->lChild;
SAFEDEL(src);
}
else //左右子树都有
{
//遍历到src左子树的前驱节点上
pTmp2 = src;
pTmp = src->lChild;
while(pTmp->rChild != NULL)
{
pTmp2 = pTmp;
pTmp = pTmp->rChild;
}
if(m_pRoot == src)
*m_pRoot = *pTmp2; //将前驱节点赋给根节点
else
*src = *pTmp2;
//if(pTmp->lChild != NULL)
pTmp2->rChild = pTmp->lChild; //正确化前驱节点的父节点指针
//else
// pTmp2->rChild = NULL;
SAFEDEL(pTmp);
}
--m_nSize;
}
7 个解决方案
#1
根据我的经验看,肯定没有这么多else if的。
#2
是是是...书上写的我看不懂,是我自己想的...
#3
先用递归实现个简单的
#4
自己想的很好,但是书上的为什么不好呢?
#5
首先要考虑删除之后当前节点的左右孩子都怎么分配,这个问题解决了就都好办了。。。而且二叉树的算法大多都是递归比较容易。。。如果闲递归效率低也可以手动递归
#6
但是...我就是想请教下,我写的是哪里出错了,哪位大侠能花点时间教教我么?
#7
没时间看你的code,但我这有个可以用的你可以参考一下
template <class T>
void BinarySearchTree<T>::remove(T d){
tree_node *curr,*parent;
curr=root;
parent=root;
//Find the node
while(curr!=NULL){
if(curr->data==d)break;
else if(curr->data>d){
parent=curr;
curr=curr->left;
}
else{
parent=curr;
curr=curr->right;
}
}
if(curr==NULL){
cout<<"Data not found!"<<endl;
return;
}
//Delete a leaf node
if(curr->left==NULL && curr->right==NULL){
if(curr==root){
delete curr;
root=NULL;
}
else if(curr->data>parent->data){
delete curr;
parent->right=NULL;
}
else {
delete curr;
parent->left=NULL;
}
}
//Delete a node with 2 children
else if(curr->left!=NULL && curr->right!=NULL){
//Find the smallest node on the right subtree
tree_node *temp=curr->right;
tree_node *temp_parent=curr;
while(temp->left!=NULL){
temp_parent=temp;
temp=temp->left;
}
//The smallest is a leaf
if(temp->left==NULL && temp->right==NULL){
if(temp_parent!=curr){
temp_parent->left=NULL;
}
else temp_parent->right=NULL;
curr->data=temp->data;
delete temp;
}
//The smallest is a node with only right subtree
else {
if(temp_parent!=curr){
temp_parent->left=temp->right;
}
else temp_parent->right=temp->right;
delete temp;
}
}
//Delete a node with only one subtree
else {
if(curr->left!=NULL){
if(curr->left->data > parent->data){
parent->right=curr->left;
}
else parent->left=curr->left;
}
else{
if(curr->right->data > parent->data){
parent->right=curr->right;
}
else parent->left=curr->right;
}
delete curr;
}
}
#1
根据我的经验看,肯定没有这么多else if的。
#2
是是是...书上写的我看不懂,是我自己想的...
#3
先用递归实现个简单的
#4
自己想的很好,但是书上的为什么不好呢?
#5
首先要考虑删除之后当前节点的左右孩子都怎么分配,这个问题解决了就都好办了。。。而且二叉树的算法大多都是递归比较容易。。。如果闲递归效率低也可以手动递归
#6
但是...我就是想请教下,我写的是哪里出错了,哪位大侠能花点时间教教我么?
#7
没时间看你的code,但我这有个可以用的你可以参考一下
template <class T>
void BinarySearchTree<T>::remove(T d){
tree_node *curr,*parent;
curr=root;
parent=root;
//Find the node
while(curr!=NULL){
if(curr->data==d)break;
else if(curr->data>d){
parent=curr;
curr=curr->left;
}
else{
parent=curr;
curr=curr->right;
}
}
if(curr==NULL){
cout<<"Data not found!"<<endl;
return;
}
//Delete a leaf node
if(curr->left==NULL && curr->right==NULL){
if(curr==root){
delete curr;
root=NULL;
}
else if(curr->data>parent->data){
delete curr;
parent->right=NULL;
}
else {
delete curr;
parent->left=NULL;
}
}
//Delete a node with 2 children
else if(curr->left!=NULL && curr->right!=NULL){
//Find the smallest node on the right subtree
tree_node *temp=curr->right;
tree_node *temp_parent=curr;
while(temp->left!=NULL){
temp_parent=temp;
temp=temp->left;
}
//The smallest is a leaf
if(temp->left==NULL && temp->right==NULL){
if(temp_parent!=curr){
temp_parent->left=NULL;
}
else temp_parent->right=NULL;
curr->data=temp->data;
delete temp;
}
//The smallest is a node with only right subtree
else {
if(temp_parent!=curr){
temp_parent->left=temp->right;
}
else temp_parent->right=temp->right;
delete temp;
}
}
//Delete a node with only one subtree
else {
if(curr->left!=NULL){
if(curr->left->data > parent->data){
parent->right=curr->left;
}
else parent->left=curr->left;
}
else{
if(curr->right->data > parent->data){
parent->right=curr->right;
}
else parent->left=curr->right;
}
delete curr;
}
}