Bài viết đang được chỉnh sửa
Binary Searched Tree
Bài toán
Lưu trữ dữ liệu theo tổ chức cây tìm kiếm, in ra cây theo các thứ tự preorder, inorder hoặc postorder.
Độ phức tạp
chèn : O(h) (với h là độ cao cây)
#include <stdio.h>
#include <vector>
using namespace std;
const int oo = 1000111000;
class bst {
public:
struct node {
int left, right, value;
node(int p) { left=right=0; value=p; }
};
vector <node*> a;
int makenew(int p){
a.push_back(new node(p));
return a.size()-1;
}
void push(int p, int u){
if (p>a[u]->value){
if (a[u]->right==0) a[u]->right = makenew(p);
else push(p, a[u]->right);
}
else {
if (a[u]->left==0) a[u]->left = makenew(p);
else push(p, a[u]->left);
}
}
void clear(){
for (int i=0; i<a.size(); i++) delete a[i];
a.clear();
}
void show(int u){
if (u==0) return ;
show(a[u]->left);
printf("%d,", a[u]->value);
show(a[u]->right);
}
void show(){
show(a[0]->left);
show(a[0]->right);
}
bst() { a.push_back(new node(-oo)); }
};
bst a;
main(){
a.push(9, 0);
a.push(4, 0);
a.push(3, 0);
a.push(5, 0);
a.show();
return 0;
}
Sample Output
3,4,5,9,
Các đặc tính khác
Kiểu vector trong C++ không thể quản lý được kiểu struct node, vì vậy, mình sử dụng vector<node*>.
BST này luôn có một nút gốc là -oo, tức là mọi nút về sau đều được đặt bên phải nút gốc này.