CTDL và giải thuật - Đếm số nụt lá

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.

Hãy đếm xem cấu trúc cây đó có bao nhiêu nút lá (nút mà không có bất kỳ nút con nào). Kết quả là một số nguyên duy nhất.

Ví dụ:

  • Test mẫu 1:
     
    Input Output

    7
    4 7 2 1 3 2 5

    3

    Với a = [4, 7, 2, 1, 3, 2, 5] thì kết quả mong muốn là 3:
    Cấu trúc cây có 3 lá như hình vẽ.

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

Ý tưởng:

Bài này ta có thể dụng đệ quy để điếm số lá trong cây t:

  • Nếu t rỗng thì countLeafNode(t) = 0.
  • Nếu t là một nút lá thì countLeafNode(n) = 1.
  • Các trường hợp còn lại thì trả countLeafNode(t->left) + countLeafNode(t->right).

Code mẫu hàm tính nút là trong cây t.

bool isLeafNode(node *l){
	return (l->left == NULL && l->right == NULL);
}
int countLeafNode(node *t){
	if (t == NULL) return 0;
	if (isLeafNode(t)) return 1;
	return countLeafNode(t->left) + countLeafNode(t->right);
}

 

Code mẫu:

Ngôn ngữ C++:

#include<iostream>

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);
		}
	}
	
}
bool isLeafNode(node *l){
	return (l->left == NULL && l->right == NULL);
}
int countLeafNode(node *t){
	if (t == NULL) return 0;
	if (isLeafNode(t)) return 1;
	return countLeafNode(t->left) + countLeafNode(t->right);
}
int main(){
	int n, temp;
	cin >> n;
	node * t = NULL;
	for (int i = 0; i < n; i++){
		cin >> temp;
		t = insert(t, temp);
	}
	cout << countLeafNode(t);
	
	return 0;
}