数据结构二叉排序树的创建、查找、删除

Myth丶恋晨 2022-06-07 12:35 172阅读 0赞

### **源代码：** ###

#include<stdio.h>
    #include<malloc.h>
     
    typedef struct Node
    {
    int key;
    struct Node* Lchild;
    struct Node* Rchild;
    }BSTNode,*BSTree;
     
    void InsertBST(BSTree *root, int key)   //二叉树插入的递归算法
    {
    if (*root == NULL)
    	{
    		*root = (BSTree)malloc(sizeof(BSTNode));
    		(*root)->key = key;
    		(*root)->Lchild = NULL;
    		(*root)->Rchild = NULL;
    	}
    else if ((*root)->key > key)
    	{
    		InsertBST(&((*root)->Lchild), key);
    	}
    else if ((*root)->key < key)
    	{
    		InsertBST(&((*root)->Lchild), key);
    	}
    }
    void CreateBSTree(BSTree* root)             //创建二叉排序树
    {
    int key;
    	scanf("%d", &key);
    while (key != -1)
    	{
    		InsertBST(root, key);
    		scanf("%d", &key);
    	}
    }
     
    void InOrder(BSTree root)
    {
    if (root != NULL)
    	{
    		InOrder(root->Lchild);
    		printf("%d ", root->key);
    		InOrder(root->Rchild);
    	}
    }
    BSTree DeleteBST(BSTree root, int key)
    {
    BSTNode *p, *f, *s, *q;
    //p是待删除节点，f是p的父节点，s是p的直接前驱，q是s的父节点
    //查找待删除节点
    	p = root;
    	f = NULL;
    while (p)
    	{
    if (p->key == key)
    		{
    break;
    		}
    		f = p;
    if (p->key > key)
    		{
    			p = p->Lchild;
    		}
    else
    		{
    			p = p->Rchild;
    		}
    	}
    //判断是否查找成功
    if (p == NULL)
    	{
    return root;//没有找到要删除的点
    	}
    //查找成功
    if (p->Lchild == NULL)
    	{
    if (f == NULL)//删除的是根节点
    		{
    return p->Rchild;
    		}
    else if (p == f->Lchild)
    		{
    			f->Lchild = p->Rchild;
    		}
    else
    		{
    			f->Rchild = p->Lchild;
    		}
    		free(p);
    	}
    else
    	{
    		s = p->Lchild;
    		q = p;
    //找直接前驱
    while (s->Rchild)
    		{
    			q = s;
    			s = s->Rchild;
    		}
    if (p == q)
    		{
    			q->Lchild = s->Lchild;
    		}
    else
    		{
    			q->Rchild = s->Lchild;
    		}
    		p->key = s->key;
    		free(s);
    	}
    return root;
    }
    int main(void)
    {
      BSTree root = NULL;
    	CreateBSTree(&root);
    	InOrder(root);       //中序遍历输出
    	printf("\n");
    	root = DeleteBST(root, 20);   //输入中有节点20 的话删除20 
    	InOrder(root);        //中序遍历输出
    return 0;
    }