NOJ数据结构025——二叉排序树的插入和删除

Bertha 。 2022-10-05 06:56 131阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]  
代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    typedef struct BiTNode {
        
    	int data;
    	struct BiTNode* left;
    	struct BiTNode* right;
    }BiTNode, * BiTree;
    
    BiTree CreateBiTree();   //创建二叉树
    void SearchAndPrint(BiTree T, int a, int b);//要求1：输出大于a、小于b的关键字
    void InsertBi(BiTree* T, int insert);//插入一个关键字并输出
    void DeleteBi(BiTree* T, int dele);  //删除结点
    void MidPrint(BiTree T); //中序输出
    
    int main()
    {
        
    	BiTree T;
    	T = CreateBiTree();
    	int a, b, insert, dele;
    	scanf("%d%d%d%d", &a, &b, &insert, &dele);
    	SearchAndPrint(T, a, b);//要求1
    	printf("\n");
    	InsertBi(&T, insert);//插入
    	MidPrint(T);//中序输出
    	printf("\n");
    	DeleteBi(&T, insert);//删除insert
    	DeleteBi(&T, dele);//删除dele
    	MidPrint(T);//中序输出
    	return 0;
    }
    
    BiTree CreateBiTree()
    {
           //创建二叉树
    	int data;
    	scanf("%d", &data);
    	if (data == -1) {
        
    		return NULL;
    	}
    	BiTree tmp;
    	tmp = (BiTree)malloc(sizeof(BiTNode));
    	if (!tmp) {
        
    		return NULL;
    	}
    	tmp->data = data;
    	tmp->left = CreateBiTree();
    	tmp->right = CreateBiTree();
    	return tmp;
    }
    
    void SearchAndPrint(BiTree T, int a, int b)
    {
           //要求1：输出大于a、小于b的关键字
    	//用中序输出
    	if (!T) {
        
    		return;
    	}
    	SearchAndPrint(T->left, a, b);
    	if (T->data > a && T->data < b) {
        
    		printf("%d ", T->data);
    	}
    	SearchAndPrint(T->right, a, b);
    }
    
    void InsertBi(BiTree* T, int insert)
    {
           //插入结点
    	if (!(*T)) {
        
    		BiTree tmp;
    		tmp = (BiTree)malloc(sizeof(BiTNode));
    		tmp->data = insert;
    		tmp->left = NULL;
    		tmp->right = NULL;
    		*T = tmp;
    		return;
    	}
    	if (insert < (*T)->data) {
        
    		InsertBi(&(*T)->left, insert);
    	}
    	if (insert > (*T)->data) {
        
    		InsertBi(&(*T)->right, insert);
    	}
    }
    
    void DeleteBi(BiTree* T, int dele)
    {
           //删除结点
    	if (!(*T)) {
        
    		return;
    	}
    	DeleteBi(&(*T)->left, dele);
    	if ((*T)->data == dele) {
        
    		if (!(*T)->left) {
        
    			//左子树为空
    			(*T) = (*T)->right;
    		}
    		else {
        //左子树非空
    			BiTree tmp = (*T)->left;
    			while (tmp->right) {
        
    				tmp = tmp->right;
    			}
    			tmp->right = (*T)->right;
    			(*T) = (*T)->left;
    		}
    		return;
    	}
    	DeleteBi(&(*T)->right, dele);
    }
    
    void MidPrint(BiTree T)
    {
           //中序输出
    	if (!T) {
        
    		return;
    	}
    	MidPrint(T->left);
    	printf("%d ", T->data);
    	MidPrint(T->right);
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl81MzA2ODI2OQ_size_16_color_FFFFFF_t_70]: /images/20221005/ada65de8951c4ede9b1de1956069737c.png