CTDL và giải thuật - In bậc của cây

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 đưa ra bậc của cây đó.

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ây được thiêt lập là:

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

bậc của một nút biểu diễn số con của một nút. Nếu nút gốc có bậc là 0, thì nút con tiếp theo sẽ có bậc là 1, và nút cháu của nó sẽ có bậc là 2, …

Ý tưởng:

Dùng đệ quy để tính bậc của một cây t.

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

Code mẫu hàm tính bậc của cây t:

bool isLeafNode(node *l){
	return (l->left == NULL && l->right == NULL);
}
int treeLevel(node *t){
	if (t == NULL) return -1;
	return 1 + max(treeLevel(t->left), treeLevel(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 treeLevel(node *t){
	if (t == NULL) return -1;
	return 1 + max(treeLevel(t->left), treeLevel(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 << treeLevel(t);
	
	return 0;
}