Xóa node trong Binary tree

Binh_Nguyen1 · May 27, 2020, 1:41pm

Các bác xem code này trước nhé

class NodeWithCount{
public:
	int key;
	int count=0;
	NodeWithCount * left, *right;
	NodeWithCount(int x)
	{
		this->key = x;
		this->left = this->right = NULL;
		this->count++;
	}
};

void inOrderWithCount(NodeWithCount * root)
{
	if (root == NULL) return;
	inOrderWithCount(root->left);
	cout << root->key << "(" << root->count << ") ";
	inOrderWithCount(root->right);
}

void insertNodeWithCount(NodeWithCount *root,int key)
{
	queue<NodeWithCount *> q;
	NodeWithCount * temp = NULL;
	q.push(root);
	while (!q.empty())
	{
		temp = q.front();
		q.pop();
		if (temp->key == key)
		{
			temp->count++;
			break;
		}
		else if(temp->key > key)
		{
			if (temp->left == NULL)
			{
				temp->left = new NodeWithCount(key);
				break;
			}
			else q.push(temp->left);
		}
		else
		{
			if (temp->right == NULL)
			{
				temp->right = new NodeWithCount(key);
				break;
			}
			else q.push(temp->right);
		}
	}
}

NodeWithCount * minValueNode(NodeWithCount* node)
{
	NodeWithCount* current = node;

	while (current->left != NULL)
		current = current->left;

	return current;
}

NodeWithCount * deleteWithCount(NodeWithCount * root, int key)
{
	if (root == NULL) return root;
	if (key < root->key) root->left = deleteWithCount(root->left, key);
	else if (key > root->key) root->right = deleteWithCount(root->right, key);
	else
	{
		if (root->count > 1)
		{
			root->count--;
			return root;
		}
		if (root->left == NULL)
		{
			NodeWithCount * temp = root->right;
			free(root);
			return temp;
		}
		else if (root->right == NULL)
		{
			NodeWithCount * temp = root->right;
			free(root);
			return temp;
		}
		NodeWithCount* temp = minValueNode(root->right);

		root->key = temp->key;

		root->right = deleteWithCount(root->right,temp->key);
	}
	return root;
}

int main()
{
	NodeWithCount * root = new NodeWithCount(12);
	root->left = new NodeWithCount(10);
	root->left->left = new NodeWithCount(9);
	root->left->right = new NodeWithCount(11);
	root->right = new NodeWithCount(20);
	insertNodeWithCount(root, 12);
	insertNodeWithCount(root, 12);
	insertNodeWithCount(root, 10);
	insertNodeWithCount(root, 14);
	inOrderWithCount(root);
	cout << endl;
	deleteWithCount(root, 9);
	inOrderWithCount(root);
	return 0;
}

Đây là code về thêm xóa Node của binary tree có thêm count các phần tử của node.

Trong func deleteWithCount(), em hơi lúng túng với recursion, ví dụ em xóa node 9 thì nó sẽ chạy từ trên xuống xong xóa root thì sao nó lại return temp->right? Tương tự với bên phải.

Với lại em giả bộ viết cái hàm deleteMin thế này:

void deleteMin(NodeWithCount * root)
{
	NodeWithCount * temp = root;
	while (temp->left != NULL)
	{
		temp = temp->left;
	}
	free(temp);
}

thế sao hàm này lại bị lỗi vậy ạ, nó báo lỗi thế này:

Nó bảo xóa rồi thì nó NULL thì ko truy cập được nữa, vậy sao hàm deleteWithCount ở trên lại truy cập được?
Mong mọi người giải đáp giúp em, em xin cảm ơn nhiều.

SITUVN.gcd · May 27, 2020, 2:06pm

Bạn chưa gán phần tử cuối cùng bằng NULL. Vì thế mà khi chạy hàm inOrderWithCount(), nó vẫn vượt qua if - return. Nhưng do bạn đã gọi free() nên việc truy xuất ô nhớ này không được phép.

Gán bằng NULL trước dòng free(temp) thử xem. Nhưng có gì đó hơi lấn cấn nhỉ.

Binh_Nguyen1 · May 27, 2020, 4:59pm

chạy được rồi mà nó ko xóa luôn nè. Với lại cấn ở chỗ hàm delete ở trên đâu cần gán cho nó bằng NULL đâu?