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

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

admin2009-05-15  67
问题 阅读以下说明和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://www.kaotiyun.com/show/QujZ777K
本试题收录于： 程序员上午基础知识考试题库软考初级分类
0

程序员上午基础知识考试

软考初级

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