dele.c

来自「二叉数插入排序,及删除算法」· C语言 代码 · 共 165 行

#include "head.h"
JD *dele(JD *tree,int data)
{
	JD  *p = NULL;
	JD  *q = NULL;
	JD  *s = NULL;
	int flag = 0;

	if(tree == NULL)
	{
		printf("二叉树为空\n");
		return NULL;
	}


	p = tree;

	if(p->data == data)
	{
		if((p->left == NULL)&&(p->right == NULL))
		{
			return NULL;
		}
		else if(p->left == NULL)
		{
			return p->right;
		}
		q = p;
		p = p->left;
		if(p->right == NULL)
		{
			q->left = p->left;
			q->data = p->data;
			free(p);
			return tree;
		}
		else
		{
			while(p->right != NULL)
			{
				s = p;
			    p = p->right;
			}
			q->data  = p->data;
			s->right = p->left;
			free(p);
			return tree;
		}


	}
			
	while((p != NULL)&&(p->data != data))
	{
		q = p;
		if(data < p->data)
		{
			p = p->left;
		}
		else
		{
				p = p->right;
		}
	}
	if(p == NULL)
	{
		printf("查无此值\n");
	}
	else if(p->data == data)
	{
		if(p->data < q->data)
		{
			if((p->left == NULL)&&(p->right == NULL))
			{
				q->left = NULL;
				return tree;
			}
			else if(p->left == NULL)
			{
				q->left = p->right;
				free(p);
				return tree;
			}
			else if(p->right == NULL)
			{
				q->left = p->left;
				free(p);
				return tree;
			}
			else
			{
				p = p->left;
				if(p->right == NULL)
				{
					q->left->left = p->left;
					q->left->data = p->data;
					free(p);
					return tree;
				}
				else
				{
					while(p->right != NULL)
					{
						s = p;
					    p = p->right;
					}
					q->left->data  = p->data;
					s->right = p->left;
					free(p);
					return tree;
				}

			}
		}
		else
		{
			if((p->left == NULL)&&(p->right == NULL))
			{
				q->right = NULL;
				return tree;
			}
			else if(p->left == NULL)
			{
				q->right = p->right;
				free(p);
				return tree;
			}
			else if(p->right == NULL)
			{
				q->right = p->left;
				free(p);
				return tree;
			}
			else
			{
				p = p->left;
				if(p->right == NULL)
				{
					q->right->left = p->left;
					q->right->data = p->data;
					free(p);
					return tree;
				}
				else
				{
					while(p->right != NULL)
					{
						s = p;
					    p = p->right;
					}
					q->right->data = p->data;
					s->right = p->left;
					free(p);
					return tree;
				}

			}

		}
	}
	
	return tree;

	
}