阅读以下说明和C++程序,将应填入(n)处的字句写在对应栏内。 【说明】以下程序实现了二叉树的结点删除算法,若树中存在要删除的结点,则删除它,否则返回。 FindNode ()函数能够在二叉树中找到给定值的结点,并返回其地址和父结点。 【C++程序】 te

admin2009-05-15  42

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

选项

答案(3)RepNodcPtr→right=DelNodePtr→right

解析 左子树没有右子结点时,则用要删除结点左子结点就是替代结点,这里将替代结点的右指针指向要删除结点的右子树,完成子树处理。
转载请注明原文地址:https://jikaoti.com/ti/6wW7FFFM
0

相关试题推荐
最新回复(0)