那个强人帮帮我 把这个程序 填完 是关于二叉树的查找的基本操作 C程序
#include <string.h>#include <malloc.h>
#include <stdio.h>
#define KEYTYPE int
typedef struct node
{KEYTYPE key;
struct node *lchild ,*rchild;
}BSTNODE;
BSTNODE *searchnode(int w, BSTNODE *r)
/*按给定值在二叉排序树中查询*/
{ BSTNODE *p;
if(r == NULL) p = NULL; /*空二叉排序树*/
else { if(w == r->key)———————— ; /*给定值和根结点相同*/
else if(w > r->key) p = searchnode(w, r->rchild); /*递归继续查询*/
else ———————— ;
}
return p;
}
BSTNODE *insert_bst(int w, BSTNODE *p)
/*将一个元素插入二叉排序树中*/
{ if(p == NULL )
{p = malloc(sizeof(BSTNODE));
p->lchild = —— ; p->rchild = —— ; p->key =—— ;}
/*如果二叉排序树空,p作为新二叉排序树的根结点*/
else if(w > p->key) p->rchild = insert_bst(w, p->rchild); /*如果二叉排序树不空,p作为叶子结点递归插入二叉排序树中*/
else p->lchild = ———— ;
return p; /*返回根结点*/
}
BSTNODE *getfather(BSTNODE *p, BSTNODE *r) /*在以r为根结点的二叉排序树中查询p结点的双亲结点并返回双亲结点的地址*/
{ BSTNODE *pf;
if(r == NULL || p == r) pf = NULL;
else
{ if(p == r->lchild || p == r->rchild) pf = r;
else if(p->key > r->key) pf = getfather(p, r->rchild);
else pf = ———— ;
}
return pf;
}
BSTNODE *dele_bst(BSTNODE *p, BSTNODE *r)
/*p结点存在,删除p结点的算法*/
{
BSTNODE *temp, *tfather, *pf;
pf= getfather(p, r); /*查找p结点的双亲结点,返回双亲结点的地址pf*/
if(p->lchild == NULL && p->rchild == NULL && pf != NULL)
/*被删结点是叶子结点,不是根结点*/
if(pf->lchild == p) pf->lchild = ———— ;
else pf->rchild = NULL;
if(p->lchild == NULL && p->rchild == NULL && pf == NULL) r =———— ;
/*被删结点是叶子结点,又是根结点*/
if(p->lchild == NULL && p->rchild != NULL && pf != NULL)
/*被删结点有右孩子,无左孩子,不是根结点*/
if(pf->lchild == p) pf->lchild = p->rchild;
else pf->rchild = p->rchild;
if(p->lchild == NULL && p->rchild != NULL && pf == NULL) r = p->rchild;
/*被删结点有右孩子,无左孩子,又是根结点*/
if(p->lchild != NULL && p->rchild == NULL && pf != NULL)
/*被删结点有左孩子,无右孩子,不是根结点*/
if(pf->lchild == p) pf->lchild = p->lchild;
else pf->rchild = p->lchild;
if(p->lchild != NULL && p->rchild == NULL && pf == NULL) r = p->lchild;
/*被删结点有左孩子,无右孩子,又是根结点*/
if(p->lchild != NULL && p->rchild != NULL)
/*被删结点又有左孩子,又有右孩子*/
{temp = p->lchild; tfather = p;
while(temp->rchild != NULL)
{
tfather = temp;
temp = temp->rchild;
}
p->key = temp->key;
if(tfather != p) tfather->rchild = temp->lchild;
else tfather->lchild = temp->lchild;
}
printf("\n");
if(r != NULL) printf("The root node of the binary sort tree is:%d\n\n", r->key);
else printf("the binary sort tree is empty\n\n");
return r;
}
void print_bst(BSTNODE *p) /*显示二叉排序树*/
{
if(p != NULL )
{ print_bst(p->lchild);
printf("%d ", ———— );
if(p->lchild != NULL)
printf("%d of the left child node is %d", p->key, ———— );
else printf("%d no left child node", p->key);
if(p->rchild != NULL)
printf("%d of the right child node is %d", p->key, ———— );
else printf("%d no right child node", p->key);
printf("\n");
print_bst(p->rchild);
}
return;
}
BSTNODE *creat_bst( ) /*建立二叉排序树*/
{
BSTNODE *root, *p;
int loop = 0;
int s;
root = ———— ;
do{ printf("\n");
printf("input datas(int,inputing zero is over): ");
scanf("%d ",—————— );
if(s == 0) loop = 1;
else
{p = searchnode(s, root);
if(p == NULL)
{ root = insert_bst(s, root);
/*输入的数据不在二叉排序树中,方可插入二叉排序树*/
print_bst(root); /*边插入边显示二叉排序树中结点值*/
}
else printf("The inputing data exist,don't insert\n");
}
if(root != NULL)
printf("\n The binary sort tree's root node is %d\n\n", root->key);
}while(!loop);
return root;
}
BSTNODE * insert(BSTNODE *root) /*将用户输入的结点插入二叉排序树中*/
{
int s;
BSTNODE *p;
printf("\n");
printf("input data(int) of inserting node: ");
scanf("%d",———— );
if(s != 0)
{ p = searchnode(s,root);
if(p == NULL)
{root = insert_bst(s,root);
/*输入的数据不在二叉排序树中,方可插入二叉排序树*/
print_bst(root); /*边插入边显示二叉排序树中结点值*/
if(root != NULL)
printf("\nThe binary sort tree's root node is %d\n\n", root->key);
}
else printf("The node exist,don't again insert!!\n");
}
return root;
}
search_bst(BSTNODE *root) /*在二叉排序树中查询用户输入的结点是否存在*/
{
int s;
BSTNODE *p;
printf("\n");
printf("input the searching node's value(int): ");
scanf("%d",&s);
if(s != 0)
{p = searchnode(s, root);
if(p == ———— ) printf("The node don't exist!\n");
else printf("The node exist!\n");}
}
BSTNODE *delete(BSTNODE *root) /*在二叉排序树中删除用户指定的结点*/
{
int s;
BSTNODE *p;
char ch;
printf("\n");
printf("input the deleting node's value(int): ");
scanf("%d", &s);
if(s != 0)
{ p = —————— ; /*用户指定要删除的结点存在吗?*/
if(p == NULL) printf("The node exist!\n\n"); /*结点不存在*/
else
{ printf("The node exist,do delete?(Y/N) ");
fflush(stdin);
scanf("%c",&ch);
if((ch=='y')||(ch =='Y')) /*结点存在,确认删除*/
{root = —————— ;
print_bst(root);
}
}
}
return root;
}
main()
{
BSTNODE *root;
int loop, i;
loop = 1;
while(loop)
{ printf("\n\n\n");
printf(" 1: The binary sort tree--- creat\n");
printf(" 2: The binary sort tree--- insert\n");
printf(" 3: The binary sort tree--- search\n");
printf(" 4: The binary sort tree--- delete\n");
printf(" 5: The binary sort tree--- print\n");
printf(" 0: quit\n");
scanf("%d",&i);
switch( —————— )
{ case 0: loop = 0; break; /*退出*/
case 1: root = creat_bst(); break; /*建立*/
case 2: root = insert(root); break; /*插入*/
case 3: search_bst(root); break; /*查找*/
case 4: root = delete(root); break; /*删除*/
case 5: printf("\n"); /*显示*/
if(root != NULL)
printf("The binary sort tree's root is %d\n",root->key); print_bst(root);
break;
}
}
return;
}
打————的地方是需要填的 先谢谢了
