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

}

}

}

//插入:在以root为根的树上插入值为item的结点

voidBSTree::InsertNode(intitem)

{

Insert(root,item);

}

//插入:在以root为根的树上插入值为item的结点

//根为空，则直接插入；根不空，则在插入之前先要查找该数值的结点是否存在

voidBSTree::Insert(BSNode*&root,intitem)

{

BSNode*newNode=NULL;

if(root==NULL)//树为空，则先建立根结点

{

newNode=newBSNode(item);

root=newNode;

cout<<item<<"已入二叉排序树中！"<<endl;

}

else

{

if(FindNode(item))//如果找到该数值的结点,直接返回

{

cout<<"数值"<<item<<"已经存在！"<<endl;

return;

}

if(item>root->data)//当前数值比根结点大，则插入树的右子树

{

Insert(root->m_rchild,item);

}

else

{

Insert(root->m_lchild,item);

}

}

}

//删除:在以root为根的树上删除值为item的结点

voidBSTree::DeleteNode(intitem)

{

Delete(root,item);

}

//删除:在以root为根的树上删除值为item的结点

voidBSTree::Delete(BSNode*&root,intitem)

{

BSNode*pNode=NULL;

if(root==NULL)

{

cout<<"树空！"<<endl;

return;

}

if(Find(root,pNode,item))

{

BSNode*pParent=NULL;

//情况一：叶子结点

if(pNode->m_lchild==NULL&&pNode->m_rchild==NULL)//被删除结点是叶子结点

{

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

{

root=NULL;

}

else//且不是根结点

{

pParent=GetParent(item);

if(pParent->m_lchild==pNode)//为其父亲结点的左孩子

{

pParent->m_lchild=NULL;

}

else//为其父亲结点的右孩子

{

pParent->m_rchild=NULL;

}

}

}

//情况二：只有一个孩子结点

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

{

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

{

root=pNode->m_rchild;

}

else//且不是根结点

{

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

if(pParent->m_lchild==pNode)

{

pParent->m_lchild=pNode->m_rchild;

}

else

{

pParent->m_rchild=pNode->m_rchild;

}

}

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