1369 - 算法9-5~9-8：二叉排序树的基本操作

8 3
1 3 5 7 8 9 10 15
9 2 5

1 0 1 

Hint

在本题中，首先需要按照题目描述中的算法完成二叉排序树的构造过程，之后需要通过在二叉排序树中的不断向下查找，将需要查询的值与当前节点的值进行比较，直到确定被查询的值是否存在。
通过课本中的性能分析部分，不难发现二叉排序树的平均查找长度是和logn同数量级的，但是，在某些特殊情况下二叉排序树将会退化，使查找的效率大大降低，这时就需要引入二叉排序树的平衡操作，利用平衡二叉树来保证查找的效率始终维持在logn的数量级上。

Solution C

//问题 C : 算法9-5~9-8：二叉排序树的基本操作
#include <stdio.h>
#include <stdlib.h>
 
typedef struct node 
{ 
    int key; 
    struct node *LChild,*RChild; 
}BSTNode,*BSTree; 
 
void CreatBST(BSTree *bst,int n);                     //创建 
BSTree SearchBST(BSTree bst,int key) ;           //查找 
void InsertBST(BSTree *bst,int key) ;            //插入 
BSTNode * DelBST(BSTree t,int k) ;               //删除 
void print_bst(BSTree t)                        //输出 
{
    if (!t)
    {
        print_bst(t->LChild);
        printf("\t%d\t", t->key);
        print_bst(t->RChild);
    }
}
 
 
/*Creat new tree*/ 
void CreatBST(BSTree *bst,int n) 
{ 
    int i; 
    int key; 
    *bst=NULL; 
    for(i=1;i<=n;i++) 
    { 
        scanf("%d",&key); 
        InsertBST(bst,key); 
    } 
    //return bst; 
} 
 
 
/*Search*/ 
BSTree SearchBST(BSTree bst,int key) 
{ 
    if(!bst)                                    //空树 
        return NULL; 
    else 
        if(bst->key==key)                               //找到则返回 
            return bst; 
        else 
            if(key <bst->key)                               //小于当前值 
                return SearchBST(bst->LChild, key);               //搜索左子树 
            else 
                return SearchBST(bst->RChild, key); 
} 
 
 
/*Insert*/ 
void InsertBST(BSTree *bst,int key) 
{ 
    BSTree t; 
    if(*bst==NULL)                            //空树，创建 
    { 
        t=(BSTree)malloc(sizeof(BSTNode)); 
        t->key=key; 
        t->LChild=NULL; 
        t->RChild=NULL; 
        *bst=t; 
    } 
    else 
        if(key <(*bst)->key)                                 //小于当前值 
            InsertBST(&((*bst)->LChild),key);                   //插入到左子树 
        else 
            if(key>(*bst)->key) 
                InsertBST(&(*bst)->RChild,key); 
} 
 
 
/*Delet*/ 
BSTNode *DelBST(BSTree t,int k) 
{ 
    BSTNode *p,*f,*s,*q; 
    p=t; 
    f=NULL; 
    while(p) 
    { 
        if(p->key==k)          //先找到删除元素在树中的位置，遍历根，左子，右子 
            break; 
        f=p; 
        if(p->key>k) 
            p=p->LChild; 
        else 
            p=p->RChild; 
    } 
    if(p==NULL)                 //没有左右子树 
        return t; 
    if(p->LChild==NULL)         //左子树为空 
    { 
        if(f==NULL) 
            t=p->RChild; 
        else 
            if(f->LChild==p) 
                f->LChild=p->RChild; 
            else 
                f->RChild=p->LChild; 
        free(p); 
    } 
    else                                //右子树为空 
    { 
        q=p; 
        s=s->LChild; 
        while(s->RChild) 
        { 
            q=s; 
            s=s->RChild; 
        } 
        if(q==p) 
            q->LChild=s->LChild; 
        else 
            q->RChild=s->LChild; 
        p->key=s->key; 
        free(s); 
    } 
    return t; 
} 
 
/*Main*/ 
int
main() 
{ 
    BSTNode *root; 
    int data,n,k;
	scanf("%d",&n); 
	scanf("%d",&k);
    CreatBST(&root,n);
    for(int j=0;j<k;j++)
    {
    	scanf("%d",&data); 
        if(SearchBST(root,data)==NULL)
        printf("0 ");
        else printf("1 ");;
		//if(root!=NULL) 
//        printf("%d ",root->key); 
//        else printf("0 ");
//        //print_bst(root);
    }
	
 
}

Solution C++

#include <cstdio>
#include <cstdlib>
#include <stack>
#include <algorithm>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)<=(b))
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status; /* 函数结果状态代码,如OK等 */
using namespace std;
typedef int KeyType; /* 设关键字域为整型 */
typedef struct
{
	KeyType key;
} ElemType; /* 数据元素类型 */
typedef ElemType TElemType;
typedef struct BiTNode {
	TElemType data;
	struct BiTNode *lchild,*rchild; /* 左右孩子指针 */
}BiTNode,*BiTree;
const int MAXN = 500;
Status InitDSTable(BiTree *DT)
{ /* 操作结果: 构造一个空的动态查找表DT */
	*DT=NULL;
	return OK;
}
void SearchBST(BiTree *T,KeyType key,BiTree f,BiTree *p,Status *flag) /* 算法9.5(b) */
{ /* 在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素，若查找 */
	/* 成功，则指针p指向该数据元素结点，并返回TRUE，否则指针p指向查找路径上 */
	/* 访问的最后一个结点并返回FALSE,指针f指向T的双亲，其初始调用值为NULL */
	if(!*T) /* 查找不成功 */
	{
		*p=f;
		*flag=FALSE;
	}
	else if EQ(key,(*T)->data.key) /*  查找成功 */
	{
		*p=*T;
		*flag=TRUE;
	}
	else if LT(key,(*T)->data.key)
		SearchBST(&(*T)->lchild,key,*T,p,flag); /* 在左子树中继续查找 */
	else
		SearchBST(&(*T)->rchild,key,*T,p,flag); /*  在右子树中继续查找 */
}
Status InsertBST(BiTree *T, ElemType e)
{ /* 当二叉排序树T中不存在关键字等于e.key的数据元素时，插入e并返回TRUE， */
	/* 否则返回FALSE。算法9.6 */
	BiTree p,s;
	Status flag;
	SearchBST(T,e.key,NULL,&p,&flag);
	if(!flag) /* 查找不成功 */
	{
		s=(BiTree)malloc(sizeof(BiTNode));
		s->data=e;
		s->lchild=s->rchild=NULL;
		if(!p)
			*T=s; /* 被插结点*s为新的根结点 */
		else if LT(e.key,p->data.key)
			p->lchild=s; /* 被插结点*s为左孩子 */
		else
			p->rchild=s; /* 被插结点*s为右孩子 */
		return TRUE;
	}
	else
		return FALSE; /* 树中已有关键字相同的结点，不再插入 */
}
void Delete(BiTree *p)
{ /* 从二叉排序树中删除结点p，并重接它的左或右子树。算法9.8 */
	BiTree q,s;
	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; /* s指向被删结点的＂前驱＂（将被删结点前驱的值取代被删结点的值） */
		if(q!=*p)
		q->rchild=s->lchild; /* 重接*q的右子树 */
		else
		q->lchild=s->lchild; /* 重接*q的左子树 */
		free(s);
	}
}
Status DeleteBST(BiTree *T,KeyType key)
{ /* 若二叉排序树T中存在关键字等于key的数据元素时，则删除该数据元素结点， */
	/* 并返回TRUE；否则返回FALSE。算法9.7 */
	if(!*T) /* 不存在关键字等于key的数据元素 */
		return FALSE;
	else
	{
		if EQ(key,(*T)->data.key) /* 找到关键字等于key的数据元素 */
			Delete(T);
		else if LT(key,(*T)->data.key)
			DeleteBST(&(*T)->lchild,key);
		else
			DeleteBST(&(*T)->rchild,key);
		return TRUE;
	}
}
int main() {
	int n, k, query, l, r, mid;
	ElemType val[MAXN];
	BiTree dt, p;
	Status flag;
	InitDSTable(&dt); /* 构造空表 */
	scanf("%d%d", &n, &k);
	for (int i = 0;i < n;i++) {
		scanf("%d", &val[i].key);
		InsertBST(&dt,val[i]); /* 依次插入数据元素 */
	}
	for (int i = 0;i < k;i++) {
		scanf("%d", &query);
		SearchBST(&dt,query,NULL,&p,&flag);
		if (flag == TRUE)
			printf("1 ");
		else
			printf("0 ");
	}
	puts("");
	return 0;
}