二叉排序树的创建和删除

实验目的

1.  掌握各种查找方法的基本思想、特点及所适应的不同场合。

2.  熟练掌握顺序查找、折半查找、索引查找、二叉排序树查找和哈希表查找算法及其实现。

3.  能用所学的查找方法解决实际问题。

实验预习

   在实验预习报告上设计，编写实验内容的源程序，给程序加上适当的注释，设计运行程序所需的测试数据。

实验内容

1.  设计并验证如下算法：二叉树采用二叉链表结构表示，按输入的关键字序列建立一棵二叉排序树，并删除该二叉排序树上的某个节点。

实验代码

#include<iostream>
#include <cstdio>
#include <malloc.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int ElemType;
typedef int KeyType;
typedef int Status;
using namespace std;

typedef struct BiNode{
	ElemType data;
	KeyType key; 
	struct BiNode * lchild;
	struct BiNode * rchild;
}BiNode,*BiTree; 

Status serachBST(BiTree T,KeyType key,BiTree f,BiTree &p){
	if(!T){
		p=f;
		return FALSE;
	}else{
		if(T->key > key){
			serachBST(T->lchild,key,T,p);
		}else if(T->key < key){
			serachBST(T->rchild,key,T,p);
		}else{
			p=T;
			return TRUE;
		}
	}
}
Status insertBST(BiTree &T,BiNode b){
	BiTree p,s; 
	if(!serachBST(T,b.key,NULL,p)){
		s=(BiTree)malloc(sizeof(BiNode));
		s->data=b.data,s->key=b.key,
		s->lchild=NULL,s->rchild=NULL;
		
		if(!p) T=s;
		else if(b.key < p->key){
			p->lchild=s;
		}else{
			p->rchild=s;
		}
		
		return TRUE;
	}else{
		return FALSE;
	}
}

void createBST(BiTree &bst){
	KeyType key;
	bst=NULL;
	BiNode b; 
	scanf("%d %d",&b.key,&b.data);
	while(b.key!=0){
		insertBST(bst,b);
		scanf("%d %d",&b.key,&b.data);
	}
}

void inOrder(BiTree T){
	if(T){
		inOrder(T->lchild);
		printf("%d ",T->key);
		inOrder(T->rchild);
	}
}

Status Delete(BiTree &p){
	BiTree s,q;
	if(!p->rchild){
		q=p;p=p->lchild;free(q);
	}else{
		if(!p->lchild){
			q=p,p=p->rchild;free(q);
		}else{
			q=p;
			s=p->lchild;
			while(s->rchild){
				q=s;
				s=s->rchild;
			}
			p->data=s->data;
			p->key=s->key; 
			if(q!=p)
				q->rchild=s->lchild;
			else q->lchild=s->lchild;
			 free(s);
		}
		return TRUE;
	}
}

Status DeleteBST(BiTree &T,KeyType key){ 
	if(!T)
		return FALSE;
	else{
		if(key==T->key)
			return Delete(T);
		else if(key < T->key)
			return DeleteBST(T->lchild,key);
		else
			return DeleteBST(T->rchild,key); 
	}
}
int main(){
	BiTree T=NULL;
	createBST(T);
	inOrder(T);
	int n=1;
	do{
		printf("\n");
		scanf("%d",&n);
		DeleteBST(T,n); 
		inOrder(T);
	}while(n);
	return 0;
}

/*
key data
样例输入 :
3 2
1 3
2 -1
7 6
7 5
9 20
-2 1
0 1
*/

运行结果：