Tóm Tắt
1. Cây nhị phân và cây nhị phân tìm kiếm
1.1 Cây nhị phân là gì ?
Cây nhị phân là cây mà mỗi nút chỉ có tối đa 2 cây con. Cây nhị phân cũng là cấu trúc thường gặp nhất trong cấu trúc cây. Một cây tổng quát trọn vẹn hoàn toàn có thể được màn biểu diễn trải qua cây nhị phân .
Ngoài cây nhị phân thường thì ra, sống sót một dạng đặc biệt quan trọng của cây nhị phân đó là cây nhị phân tìm kiếm. Chúng ta sẽ thao tác hầu hết trên cây nhị phân tìm kiếm !
1.2 Cây nhị phân tìm kiếm là gì ?
Cây nhị phân tìm kiếm ( BST ) là một dạng đặc biệt quan trọng của cây nhị phân trong đó thỏa mãn nhu cầu theo nguyên tắc :Cây nhị phân tìm kiếm ứng với n khóa k1, k2, k3 … kn là cây nhị phân mà mỗi nút đều được gán một khóa sao cho với mỗi một nút k :
- Mọi khóa trên cây con trái đều nhỏ hơn khóa trên nút k
- Mọi khóa trên cây con phải đều lớn hơn khóa trên nút k
Các phép toán trên cây nhị phân tìm kiếm :
- Chèn phần tử vào cây
- Duyệt cây
- Xóa phần tử
- Tìm kiếm phần tử
- Sắp xếp
Các phép toán trên được nêu rõ hơn trong những bài tiếp theo, trong bài này ta sẽ cùng setup cấu trúc cây để tiện thao tác với những phép toán ở trên !
2. Một số đặc thù cây nhị phân
Dưới đây là 1 số ít đặc thù của cây nhị phân :
- Số nút nằm ở mức i ≤ 2i
- Chiều cao của cây là mức cao nhất + 1.
- Chiều cao của cây ≥ log2 (số nút trong cây)
- Số nút lá ≤ 2h-1, với h là chiều cao của cây
- Số nút trong ≤ 2h-1
- Đường đi (path): Tên các nút của quá trình đi từ nút gốc theo các cây con đến một nút nào đó
3. Biểu diễn cây nhị phân tìm kiếm bằng C / C + +
3.1 Biểu diễn cây nhị phân trải qua node
Để màn biểu diễn cây nhị phân trong C / C + + ta cần có một node gồm có những thành phần đó là : thành phần tài liệu của node, thành phần địa chỉ nút gốc của cây con trái trong bộ nhớ và thành phần địa chỉ nút gốc của cây con phải trong bộ nhớ .
Trong hình trên :
- A, B, C, D, E G là thành phần dữ liệu của node.
- Các node luôn có 2 con trỏ để trỏ đến cây con trái và cây con phải.
- Trong trường hợp không tồn tại cây con trái (hoặc cây con phải) của 1 node thì con trỏ của node đó sẽ được trỏ về giá trị NULL
Đoạn code dưới đây sẽ giúp ta khai báo một node trong cây nhị phân bằng C / C + +
typedef struct Node{
//khai bao du lieu cua node co kieu du lieu int
int data;
//khai bao con tro den cay con trai
Node* left;
//khai bao con tro den cay con phai
Node* right;
};
typedef struct Node* Tree;
Tree root;
3.2 Hàm khởi tạo cây nhị phân
Cây nhị phân khi mới được khởi tạo sẽ chưa có node nào vì vậy việc khởi tạo cây chỉ đơn giản là ta sẽ gán cho con trỏ quản lý node gốc (hay root) của cây về giá trị NULL.
void Init (Tree &root){
//gan node goc ve NULL
root = NULL;
}
3.3 Hàm tạo một node mới trong cây nhị phân
Như đã đề cập ở phần trên, một node của cây nhị phân gồm có : thành phần tài liệu của node, thành phần địa chỉ nút gốc của cây con trái trong bộ nhớ và thành phần địa chỉ nút gốc của cây con phải trong bộ nhớ. Vì vậy mà ta cần có một hàm tạo node để khai báo những thành phần trên .
Node* CreateNode (int x){
//tao node moi
Node* p = new Node;
//neu node p duoc cap phat bo nho
if (p != NULL){
//gan cay con trai va cay con phai mac dinh bang NULL
p->left = NULL;
p->right = NULL;
//gan data bang x
p->data = x;
}
//tra ve node p
return p;
}
4. Chương trình hoàn hảo setup cây nhị phân bằng C / C + +
Chương trình dưới đây sử dụng lại toàn bộ những hàm trên để đưa ra một chương trình hoàn hảo về việc thiết lập cây nhị phân trong C / C + +
#include#include typedef struct Node{ //khai bao du lieu cua node co kieu du lieu int int data; //khai bao con tro den cay con trai Node* left; //khai bao con tro den cay con phai Node* right; }; typedef struct Node* Tree; Tree root; void Init (Tree &root){ //gan node goc ve NULL root = NULL; } Node* CreateNode (int x){ //tao node moi Node* p = new Node; //neu node p duoc cap phat bo nho if (p != NULL){ //gan cay con trai va cay con phai mac dinh bang NULL p->left = NULL; p->right = NULL; //gan data bang x p->data = x; } //tra ve node p return p; } int main(){ //tao cay voi node goc la root Tree root; //khoi tao cay Init(root); }
Chú ý rằng, chương trình dưới đây chỉ dừng lại ở mức thiết lập một cấu trúc cây. Các thao tác với cây nhị phân sẽ được nêu rõ hơn ở những bài tiếp theo !
Source: https://final-blade.com
Category : Kiến thức Internet
