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 53
Vớia = [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;
}