实验8搜索二进制排序树

首先，实验目的

1. 掌握二进制排序树的含义及其在计算机中的存储实现.

2. 掌握二元排序树上搜索操作的算法实现.

3. 掌握二进制排序树的插入和删除的算法实现.

第二，实验内容

1. 建立一个二进制排序树.

2. 给定值的搜索操作在二进制排序树上实现.

3. 在二进制排序树上插入和删除指定的节点.

三，实验要求

1. 建立一个二进制排序树.

根据n个关键字的输入顺序构建一个二进制排序树. 二进制排序树使用二进制链表的存储结构.

2. 给定值的搜索操作在二进制排序树上实现.

首先输入要搜索的记录的键值，然后在二进制排序树中搜索记录. 如果该记录存​​在于二进制排序树中，则将显示消息“找到”，否则将显示“未找到”“信息”.

3. 在二进制排序树上插入和删除指定的节点.

（1）输入要插入的记录的键值二叉排序树查找，然后在二进制排序树中搜索该记录. 如果搜索失败，则在二进制排序树中插入与记录对应的节点，并在二进制排序树之后（按遍历顺序）输出插入操作.

（2）输入要删除的记录的键值，然后在二进制排序树中搜索该记录. 如果搜索成功，则删除二进制排序树中与记录相对应的节点，并在二进制排序树之后（按遍历顺序）输出删除操作.

四个详细的程序列表

//二叉排序树 
#include<stdio.h>  
#include<stdlib.h>  
typedef struct BiTNode  
{  
    int key;  
    struct BiTNode *lchild, *rchild;  
} BiTNode, *BiTree;  
  
int SearchBST(BiTree T,int key,BiTree f,BiTree &p )//查找 
{  
	 if(!T)  {p=f;return 0;}
   		else if (key==T->key) {p=T;return 1;}
    		else if(key<T->key) SearchBST(T->lchild,key,T,p);
               else SearchBST(T->rchild,key,T,p); 
}
  
int InsertBST(BiTree &T,int key)//插入 
{  
    if(!T)
    {  
        T=(BiTree)malloc(sizeof(BiTNode)); 
        T->key=key;  
        T->lchild=(T)->rchild=NULL;  
    }  
    if(key==T->key) return 0;  
    if(key>T->key) InsertBST(T->rchild,key); 
    else InsertBST(T->lchild,key); 
}  
  
void InorderTraverse(BiTree T)//中序遍历
{  
     if(T)
     {  
          InorderTraverse(T->lchild);
          printf("%d ",T->key);
          InorderTraverse(T->rchild);
     }
}
void Delete(BiTree &p) //删除 
{  
    BiTree q, s;  
    if(!p->lchild &&!p->rchild) //p为叶子节点  
        p = NULL; 
    else if(!p->lchild) //左子树为空，重接右子树
    {  
        q=p;   
        p=p->rchild;  
        free(q);  
    }  
    else if(!p->rchild) //右子树为空，重接左子树
    {  
        q=p;  
        p=p->lchild; 
        free(q);  
    }  
    else  //左右子树均不为空   
    {  
        q=p;  
        s=p->lchild;  
        while(s->rchild)
        {  
            q=s;  
            s=s->rchild;  
        }  
        p->key=s->key;  
        if(q!=p)
            q->rchild=s->lchild; 
        else  
            q->lchild=s->lchild;
        free(s);  
    }  
}  
  
int DeleteBST(BiTree &T, int key)//删除 
{  
    if(!T) return 0;
    else  
    {  
        if(key==T->key ) Delete(T);  
        else if(key<T->key)  DeleteBST(T->lchild,key);  
        else  DeleteBST(T->rchild,key);  
    }  
}  
  
int main()  
{  
    int e,n;  
    BiTree T=NULL,f,p; 
    printf("输入长度：");
	scanf("%d",&n); 
	printf("输入元素：");
 	while(n--)
 	{
 		scanf("%d",&e); 
    	InsertBST(T, e);  
 	}
    printf("中序遍历：");  
    InorderTraverse(T);
    printf("\n"); 
    while(1)
	{
		printf("输入要查找元素：");
		scanf("%d",&e); 
		if(SearchBST(T,e,f,p)) printf("找到了\n");
		else printf("没找到\n");
		printf("输入要插入元素：");
		scanf("%d",&e); 
		InsertBST(T,e);
		printf("中序遍历：");  
    	InorderTraverse(T);
    	printf("\n");  
		printf("输入要删除元素：");
		scanf("%d",&e); 
    	DeleteBST(T,e);
    	printf("中序遍历：");  
    	InorderTraverse(T);
    	printf("\n");  
	}
} 

五个程序运行结果

六. 实验经验

1. 啊. . . 我饿了二叉排序树查找，去吃饭了.

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