【说明】以下程序实现了二叉树的结点删除算法，若树中存在要删除的结点，则删除它，否则返回。 FindNode ()函数能够在二叉树中找到给定值的结点，并返回其地址和父结点。
【C++程序】
template ＜ class T ＞
void BinSTree ＜ T ＞: :Delete( const T& item)
{
TreeNode ＜ T ＞ * DelNodePtr, * ParNodePtr, * RepNodePtr;
if(( DelNodePtr = FindNode (item,ParNodePtr)) = = NULL)
{{U}}(1) {{/U}}
if(DelNodePtr→right = = NULL) //被删除结点只有一个子结点的情况
RepNodePtr = DelNodePtr→left;
else if( DelNodePtr→left = = NULL)
{{U}}(2) {{/U}};
else // 被删除结点有两个子结点的情况
{
TreeNode ＜ T ＞* PofRNodePtr = DelNodePtr;
RepNodePtr = DelNodePtr→left;
while(RepNodePtr→right ! = NULL)
{ //定位左子树的最右结点
PofRNodePtr =RepNodePtr;
RepNodePtr = RepNodePtr→right;
}
if(PofRNodePtr = = DelNodePtr) //左子树没有右子结点
{{U}}(3) {{/U}};
else //用左子顷的最右结点替换删除的结点
{
{{U}}(4) {{/U}}
RepNodePtr→left = DelNodePtr→left;
RepNodePtr→right = DelNodePtr→right;
}
}
if{{U}} (5) {{/U}}//要删除结点是要结点的情况
root = RepNodePtr;
else if ( DelNodePtr→data ＜ ParNodePtr→Data)
ParNodePtr→left = RepNodePtr;
else
ParNodePtr→right =RepNodePtr;
FirstTreeNode ( DelNodePtr ) ;//释放内存资源
size→;
}