数据结构第九章填空题及参考答案[9]_跨考网

1．假设root是一棵给定的非空查找树，对于下面给出的子程序，当执行注释中给出的调用语句时，就可以实现如下的操作：在非空查找树root中查找值为k 的结点；若值为k的结点在树中，且是一个叶子结点，则删除此叶子结点，同时置success

　　为“真”；若值为k的结点不在树中，或者虽然在树中，但不是叶子结点，则不进行删除，仅置success为“假”。应注意到非空查找树只包含一个结点情况，此时树中的唯一结点，既是根结点，也是叶子结点。

　　#include <stdio.h>

　　typedef struct node {

　　int key;

　　struct node *left， *right;

　　} node;

　　node *root; int k，success;

　　void del_leaf(node **t, int k, int *sn)

　　{ node *p, *pf; p=*t; *sn=0;

　　while(_（1）_&&!*sn)

　　if (k==p->key) *sn =1;

　　else { _（2）_;

　　if (k<p->key ) p=p->left; else p=p->right; }

　　if (*sn && p->left==NULL && p->right==null)

　　{ if (_（3）_ )

　　if (pf->left ==p ) pf ->left=null; else pf->right=null;

　　else _（4）_ ;

　　free(p); }

　　else *sn=0;

　　/*call form :del_leaf( &root, k, &success);*/ 【上海大学 1999 一、2 （8分）】

　　【参考答案】

　　(1)p!=null (2)pf=p (3)p!=*t (4)*t=null