二叉排序树的插入与删除

分手后的思念是犯贱 2022-08-02 13:34 179阅读 0赞

二叉排序树的插入与删除可能会破坏二叉排序树的性质，现在要求插入和删除操作保持其性质

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：  
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；  
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；  
（3）左、右子树也分别为二叉排序树；  
（4）没有键值相等的节点。

#include "stdafx.h"
    #include<iostream>   
    using namespace std;
    
    
    struct BiNOde
    {
    	int ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    
    
    BiNOde* nearnode = NULL;
    int min = 100000;
    BiNOde*tobedeleted = NULL;
    BiNOde*parentoftobedeleted = NULL;
    
    
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	BiNOde*node12 = new BiNOde;
    	root->ele = 45;
    	node1->ele = 38;
    	node2->ele = 55;
    	node3->ele = 33;
    	node4->ele = 41;
    	node5->ele = 19;
    	node6->ele = 16;
    	node7->ele = 52;
    	node8->ele = 58;
    	node9->ele = 50;
    	node10->ele = 44;
    	node11->ele = 35;
    	node12->ele = 42;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = NULL;//node11;
    	node4->rnode = node10;
    	node4->lnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = node12;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;    
    	//node12->ele = 12;    
    	node12->lnode = NULL;
    	node12->rnode = NULL;
    	//node6->lnode = node11;    
    	return root;
    }
    
    
    
    
    void find(BiNOde*node, int value)
    {
    	if (node == NULL)
    		return;
    	int k = node->ele - value;
    	if (k > 0)
    		if (k < min)
    		{
    			min = k;
    			nearnode = node;
    		}
    	find(node->lnode, value);
    	find(node->rnode, value);
    
    
    }
    
    
    
    
    BiNOde*insert(BiNOde*root, int value)
    {
    	BiNOde* p = new BiNOde;
    	p->ele = value;
    	BiNOde*n;
    	find(root, value);
    
    
    	n = nearnode->lnode;
    	nearnode->lnode = p;
    	p->lnode = n;
    	p->rnode = NULL;
    	return root;
    }
    
    
    
    
    void searchnode(BiNOde*root, int value)
    {
    	tobedeleted = root;
    	while (tobedeleted->ele != value)
    	{
    		parentoftobedeleted = tobedeleted;
    		if (tobedeleted->ele > value)
    			tobedeleted = tobedeleted->lnode;
    		else
    			tobedeleted = tobedeleted->rnode;
    	}
    }
    
    
    
    
    
    
    BiNOde*delete_node(BiNOde*root, int value)
    {
    	BiNOde*minnode, *maxnode, *nn = NULL;
    	searchnode(root, value);
    	if (tobedeleted == root)
    	{
    		if (root->lnode == NULL)
    		{
    			root = root->rnode;
    			delete tobedeleted;
    			return root;
    		}
    		maxnode = root->lnode;
    		if (maxnode->rnode == NULL)
    		{
    			maxnode->rnode = root->rnode;
    			root = maxnode;
    			delete tobedeleted;
    			return root;
    		}
    		while (maxnode->rnode != NULL)
    		{
    			nn = maxnode;
    			maxnode = maxnode->rnode;
    		}
    		nn->rnode = maxnode->lnode;
    		maxnode->lnode = root->lnode;
    		maxnode->rnode = root->rnode;
    		root = maxnode;
    		delete tobedeleted;
    		return root;
    	}
    
    
    	if (tobedeleted->lnode == NULL&&tobedeleted->rnode == NULL)
    	{
    		if (parentoftobedeleted->lnode == tobedeleted)
    		{
    
    
    			parentoftobedeleted->lnode = NULL;
    			delete tobedeleted;
    			return root;
    		}
    		else
    		{
    			parentoftobedeleted->rnode = NULL;
    			delete tobedeleted;
    			return root;
    		}
    	}
    
    
    	if (tobedeleted->lnode == NULL)
    	{
    		minnode = tobedeleted->rnode;
    		if (minnode->lnode != NULL)
    		{
    			while (minnode->lnode != NULL)
    			{
    				nn = minnode;
    				minnode = minnode->lnode;
    			}
    			nn->lnode = minnode->rnode;
    		}
    		if (parentoftobedeleted->lnode == tobedeleted)
    		{
    			parentoftobedeleted->lnode = minnode;
    		}
    		else
    		{
    			parentoftobedeleted->rnode = minnode;
    		}
    		if (minnode != tobedeleted->rnode)
    			minnode->rnode = tobedeleted->rnode;
    		delete tobedeleted;
    		return root;
    	}
    
    
    
    
    	maxnode = tobedeleted->lnode;
    	if (maxnode->rnode != NULL)
    	{
    		while (maxnode->rnode != NULL)
    		{
    			nn = maxnode;
    			maxnode = maxnode->rnode;
    		}
    		nn->rnode = maxnode->lnode;
    	}
    	if (parentoftobedeleted->lnode == tobedeleted)
    	{
    		parentoftobedeleted->lnode = maxnode;
    	}
    	else
    	{
    		parentoftobedeleted->rnode = maxnode;
    	}
    	if (maxnode != tobedeleted->lnode)
    	{
    		maxnode->lnode = tobedeleted->lnode;
    		maxnode->rnode = tobedeleted->rnode;
    	}
    	else
    	{
    		maxnode->rnode = tobedeleted->rnode;
    	}
    	delete tobedeleted;
    	return root;
    
    
    }
    
    int _tmain(int argc, _TCHAR* argv[])
    {
    	BiNOde*root = create_tree();
    	//insert(root, 37);
    	root = delete_node(root, 38);
    	cout << root->ele << endl;
    	system("pause");
    	return 0;
    }

欢迎大家指错或提出改进意见