关于二叉树与二叉搜索树!

对于二叉搜索树,我们如果要删除一个节点,需要我们比较左右节点大小来找到这个节点,然后再有三种情况,无孩子,一个孩子,两个孩子。

但是,如果针对任意的二叉树(非二叉搜索树),那么如果要删除任意数据,应该怎么C代码实现呢?

我自己写了一个,不知可不可行,大神来给意见呐!

以下是删除功能的代码

struct Node *Find(struct Node *root)
{
	while (root -> left != NULL) root = root -> left;
	return root;
}
struct Node *Delete(struct Node *root, int data)
{
	if (root == NULL) return root;
	if (root -> data != data) 
	{
		root -> left = Delete(root -> left, data);
		root -> right = Delete(root -> right, data);
	}
	//wohoo....i found you,get ready to delete!
	else
	{
	        //case 1 : no child
		if (root -> left == NULL && root -> right == NULL)
		{
			free(root);//C++ --> delete root;
			root = NULL;
		}
		//case 2 : one child
		else if (root -> left == NULL)
		{
			struct Node *temp = root;
			root = root -> right;
			free(temp);//C++ --> delete root;		
		}
		else if (root -> right == NULL)
		{
			struct Node *temp = root;
			root = root -> left;
			free(temp);//C++ --> delete root;
		}
		else//case 3 : two children
		{
			struct Node *temp = Find(root);//find a data to replace this deleted data
			root -> data = temp -> data;
			root -> left = Delete(root -> left, temp -> data);//Delete the data I found on the left
		}
	}
	return root;
}


asdhjhg
浏览 1544回答 0
0回答
打开App,查看更多内容
随时随地看视频慕课网APP