二叉排序树的实现_折半查找方法的实现_c二叉树非递归中序遍历(4)

}

elseif(pNode->m_lchild!=NULL&&pNode->m_rchild==NULL)//被删结点有左孩子,无右孩子

{

if(pNode==root)//且是根结点

{

root=pNode->m_lchild;

}

else//且不是根结点

{

pParent=GetParent(item);//找到给结点的父亲节点

if(pParent->m_lchild==pNode)

{

pParent->m_lchild=pNode->m_lchild;

}

else

{

pParent->m_rchild=pNode->m_lchild;

}

}

}

//情况三：有两个孩子结点

elseif(pNode->m_lchild!=NULL&&pNode->m_rchild!=NULL)//被删结点有左孩子和右孩子

{

//解法一：找到该结点的前驱结点(右孩子必为空)

BSNode*maxNode=NULL;

intmax=Max(pNode->m_lchild,maxNode);//找到以该结点左孩子为根的子树上最大的结点，即为其前驱结点

BSNode*father=GetParent(max);

pNode->data=max;//将前驱结点的值赋给该结点

if(father!=pNode)

{

father->m_rchild=maxNode->m_lchild;

}

else

{

father->m_lchild=maxNode->m_lchild;

}

//解法二：找到该结点的后继结点(左子树必为空)

//BSNode*minNode=NULL;

//intmin=Min(pNode->m_rchild,minNode);//找到以该结点右孩子为根的子树上最小的结点，即为其后继结点

//BSNode*father=GetParent(min);

//pNode->data=min;//将后继结点的值赋给该结点

//if(father!=pNode)

//{

//father->m_lchild=minNode->m_rchild;

//}

//else

//{

//father->m_rchild=minNode->m_rchild;

//}

//解法三：让该结点的左子树为其父亲结点的左子树(或右子树,取决于该结点是父亲结点的左子树还是右子树)，

//其右子树为其前驱结点(以该结点左孩子为根的子树中最大值结点)的右子树

//BSNode*Father=GetParent(item);

//if(Father==NULL)//该结点是根结点

//{

//root=pNode->m_lchild;

//BSNode*maxNode=NULL;

//intmax=Max(pNode->m_lchild,maxNode);

//maxNode->m_rchild=pNode->m_rchild;

//}

//else//该结点不是根结点

//{

//if(Father->m_lchild==pNode)

//{

//Father->m_lchild=pNode->m_lchild;

//}

//else

//{

//Father->m_rchild=pNode->m_lchild;

//}

////BSNode*maxNode=GetInOrderPre(item);

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-25453-4.html