CTDL và giải thuật - Xóa những node có giá trị bằng x

Cho một dãy gồm n số nguyên, hãy cài đặt dãy đó vào cây nhị phân tìm kiếm bằng cách sau, phần tử đầu tiên được chọn làm gốc, các phần tử tiếp theo được chèn và cây nhị phần theo cách: node con bên trái luôn nhỏ hơn node cha, node con bên phải luôn lớn hơn học bằng node cha.

Cuối cùng nhập một sô nguyên x, hãy xóa những node có giá trị bằng x (các node con của nó cũng bị xóa theo). In các phần tử trong cây theo cách duyệt trung thứ tự. Nếu cây rỗng in ra "NULL".

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    7
    5 2 7 1 3 2 4
    3

    1 2 5 7

    Với a = [5, 2, 7, 1, 3, 2, 4] và x = 3 thì kết quả mong muốn là: "1 2 5 7 ".
    Hình ảnh của cây nhị phân.

  • Khi đã xóa node có giá trị 3.

  • Với a = [1, 2, 3] và x = 1 thì kết quả mong muốn là "NULL".

Hướng dẫn bài tập.

Code mẫu hàm xóa node trong cây nhị phân.

void deleteNode(node *t){
	if(t != NULL){
		if (t->left != NULL) deleteNode(t->left);
		if (t->right != NULL) deleteNode(t->right);
		delete(t);
	}
}

Code mẫu:

Ngôn ngữ C++:

#include<iostream>
#include<math.h>

using namespace std;

struct node{
	int data;
	node *left;
	node *right;
};
node *insert(node *t, int x){
	if (t == NULL){
		node *temp = new node;
		temp->data =x;
		temp->left = NULL;
		temp->right = NULL;
		return temp;
	} else{
		if (x < t->data){
			t->left = insert(t->left, x);
		} else{
			t->right = insert(t->right, x);
		}
	}
}
void printTree(node *t){
	if (t != NULL){
		printTree(t->left);
		cout << t->data << " ";
		printTree(t->right);
	}
}
void deleteNode(node *t){
	if(t != NULL){
		if (t->left != NULL) deleteNode(t->left);
		if (t->right != NULL) deleteNode(t->right);
		delete(t);
	}
}
node *deleteNumber(node *t, int x){
	if (t != NULL){
		if (t->data == x){
			deleteNode(t->left);
			deleteNode(t->right);
			t = NULL;
		}
		else if (t->data > x) t->left = deleteNumber(t->left, x);
		else t->right = deleteNumber(t->right, x);		
	}
	return t;
}
int main(){
	int n, x, temp;
	cin >> n;
	node * t = NULL;
	for (int i = 0; i < n; i++){
		cin >> temp;
		t = insert(t, temp);
	}
	cin >> x;
	t = deleteNumber(t, x);
	if (t == NULL) cout <<"NULL";
	else printTree(t);
	return 0;
}