二叉排序树(C语言)

代码中用到了二级指针,由于如果只传入一级指针,是无法在保留方法中malloc分配的内存,方法执行结束就系统返还内存,所以需要用到二级指针,创建二叉排序树时传入二级指针,通过(*BST)的方法创建对象,一定要加括号

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>

typedef int  ElemType;
typedef int KeyType ;
typedef struct BSTNode
{
    
    int data;
    struct BSTNode *lchild;
    struct  BSTNode *rchild;
} BSTNode,*BSTree;


void InOrderTraverse(BSTree T)
{
    

    if(T!=NULL)
    {
    
        InOrderTraverse(T->lchild);
        printf("%d-->",T->data);
        InOrderTraverse(T->rchild);
    }
}


//非递归搜索
BSTNode *BST_Search(BSTree T,ElemType  key)
{
    

    while(T!=NULL&&key!=T->data)
    {
    
        if(key<T->data)T=T->lchild;
        else T=T->rchild;
    }
    return T;
}

//插入
bool  BST_Insert(BSTree *T,KeyType k)
{
    

    if(*T==NULL)
    {
    
        *T=(BSTree)malloc(sizeof(BSTNode));
        (*T)->data=k; //二级指针必须加括号
        (*T)->lchild=(*T)->rchild=NULL;
        return true;
    }
    else if(k==(*T)->data)return false;//已经存在
    else if(k<(*T)->data)return BST_Insert(&(*T)->lchild,k);
    else return BST_Insert(&(*T)->rchild,k);
}



//将待删除结点的左子树最右侧结点,作为拼接结点
void  Delete_Node(BSTree *p)
{
    
    BSTree q,s;
    if(!(*p)->lchild)//左子树为空
    {
    
        q=*p;
        *p=(*p)->rchild;
        free(q);
    }
    else if(!(*p)->rchild)  //右子树为空
    {
    

        q=*p;
        *p=(*p)->lchild;
        free(q);
    }
    else
    {
    
        s=(*p)->lchild;
        while(s->rchild)s=s->rchild;
        s->rchild=(*p)->rchild;//将p的右子树,连接到s的右子树上
        q=(*p);
        *p=(*p)->lchild;//重新拼接
        free(q);//删除当前节点
    }
}


//找到左子树最右侧结点
bool BST_Delete(BSTree *T,KeyType key)
{
    

    if(*T==NULL)return false;
    else
    {
    
        if(key==(*T)->data)
        {
    
            Delete_Node(&(*T));
            return true;
        }
        else if(key<(*T)->data)
            return BST_Delete(&(*T)->lchild,key);
        else  return BST_Delete(&(*T)->rchild,key);
    }
}


BSTree Create_BSTree(int *arr,int len)
{
    
    BSTree T=NULL;
    for(int i=0; i<len; i++)
        BST_Insert(&T,arr[i]);
    return T;
}


int main()
{
    


    int num;
    printf("请输入节点个数: \n");
    scanf("%d",&num);

    int *arr=(int*)malloc(num*sizeof(int));
    printf("依次输入数据\n");
    for(int i=0; i<num; i++)
        scanf("%d",arr+i);
    BSTree T=Create_BSTree(arr,num);
    printf("中序遍历二叉排序树结果:\n");
    InOrderTraverse(T);
    printf("\n");


    int key;
    printf("请输入要查找的整数：");
    scanf("%d",&key);

    if(BST_Search(T,key))
        printf("查找成功\n");
    else
        printf("查找不到该整数\n");


    printf("请输入要插入的整数：");
    scanf("%d",&key);
    if(BST_Insert(&T,key))
    {
    
        printf("插入成功，插入后的中序遍历结果：");
        InOrderTraverse(T);
        printf("\n");
    }
    else
        printf("插入失败，该二叉排序树中已经存在整数%d\n",key);


    //删除给定的整数
	printf("请输入要删除的整数：");
	scanf("%d",&key);
	if(BST_Delete(&T,key))
	{
    
		printf("删除成功，插入后的中序遍历结果：");
		InOrderTraverse(T);
		printf("\n");
	}
	else
		printf("删除失败，该二叉排序树中不存在整数%d\n",key);





}