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

{

pParent=root;

}

elseif(root->data>item)

{

pParent=getParent(root->m_lchild,item);

}

else

{

pParent=getParent(root->m_rchild,item);

}

}

returnpParent;

}

else

{

cout<<"不存在值为"<<item<<"的结点！";

returnpParent;

}

}

//获取中序遍历的前驱结点

BSNode*BSTree::GetInOrderPre(intitem)

{

returngetInOrderPre(root,item);

}

//获取中序遍历的前驱结点

//思想：先找到对应的结点，如果该结点的左孩子不空，找到以它的左孩子为根的子树中的最大值结点

//否则如果该结点的左孩子空，找到第一个有右孩子的祖先结点

BSNode*BSTree::getInOrderPre(BSNode*root,intitem)

{

BSNode*pPre=NULL;//指向该结点的前驱结点的指针

BSNode*pNode=NULL;

if(Find(root,pNode,item))//找到对应的结点

{

if(pNode->m_lchild!=NULL)//该结点的左孩子不空

{

BSNode*maxNode=NULL;

intmax=Max(pNode->m_lchild,maxNode);//找到以它的左孩子为根的子树中的最大值结点

pPre=maxNode;

}

else//该结点的左孩子为空

{

//找到第一个有右孩子的祖先结点

BSNode*pParent=GetParent(item);

;

while(pParent->m_rchild==NULL)//右孩子为空

{

pParent=GetParent(pParent->data);

}

pPre=pParent;

}

returnpPre;

}

else

{

cout<<"数值为"<<item<<"的结点不存在！";

returnpNode;

}

}

//获取中序遍历的后继结点

//思想：先找到对应的结点，如果右孩子节点非空，则找到右子树的最小值节点

//否则如果右孩子节点为空，则找到第一个有左孩子节点的其祖辈节点

BSNode*BSTree::GetInOrderPost(intitem)

{

returngetInOrderPost(root,item);

}

//获取中序遍历的后继结点

BSNode*BSTree::getInOrderPost(BSNode*root,intitem)

{

BSNode*pPost=NULL;//指向后继结点的指针

BSNode*pNode=NULL;

if(Find(root,pNode,item))

{

if(pNode->m_rchild!=NULL)//该结点的右孩子不空

{

//找到以其右孩子为根的子树中最小值的结点

BSNode*minNode=NULL;

intmint=Min(pNode->m_rchild,minNode);

pPost=minNode;

}

else//该结点的右孩子为空

{

//找到第一个有左孩子的祖先结点

BSNode*pParent=GetParent(item);

while(pParent->m_lchild==NULL)

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