Đối với môn Cấu trúc dữ liệu (CTDL), cây là một trong những khái niệm đặc biệt quan trọng, đặc biệt là cây nhị phân tìm kiếm (binary search tree - BST). Để có thể hiểu được BST, bạn cần phải hiểu rõ các loại danh sách liên kết (như đơn, đôi v.v...), và tất nhiên, phải hiểu rất rõ con trỏ cũng như cách sử dụng con trỏ.
Cây đơn giản là một cấu trúc dữ liệu bao gồm các nút, mỗi nút có thể coi là một ô nhớ chứa ít nhất là một biến dữ liệu và các con trỏ lưu giữ địa chỉ của các nút kết tiếp.
Cây nhị phân là cây mà mỗi nút của nó chỉ có tối đa 2 nút con.
Cây nhị phân tìm kiếm là cây nhị phân có quy luật như sau:
▸Khóa (hay giá trị) của một nút bất kỳ bên nhánh trái phải nhỏ hơn khóa (hay giá trị) của nút cha trên nó.
▸Khóa (hay giá trị) của một nút bất kỳ bên nhánh phải phải lớn hơn khóa (hay giá trị) của nút cha trên nó.
Lý thuyết cơ bản nói chung là như vậy, bây giờ chúng ta cần phải cài đặt thử một cây nhị phân bằng C++ xem nó như thế nào nhé.
Tạo một mảng các số nguyên với thứ tự đầu vào các số như sau:
short a[] = {29, 5, 39, 19, 11, 10, 18, 25, 0, 1, 23, 34, 48, 6, 24, 26};
Dựa vào quy luật của BST, ta có được hình minh họa như sau:
Khai báo cấu trúc của một node trong cây nhị phân tìm kiếm:
struct node {
short x;
node *left;
node *right;
};
Tạo node mới:
// create a new node
node* createNode(short x) {
node *p = new node();
p->x = x;
p->left = NULL;
p->right = NULL;
}
Chèn một node vào cây nhị phân tìm kiếm:
// find a good node to insert the next new node
node* findPosition(node* root, short x) {
node *p = root;
while (p != NULL) {
// q points to the node which p is currently pointing to
// before p points to another node
node *q = p;
if (p->x > x) {
p = p->left;
} else {
p = p->right;
}
if (p == NULL) { // no more nodes to point to
return q;
}
}
}
void insertNode(node *&root, short x) {
if (root == NULL) { // the tree has no nodes
root = createNode(x);
return;
} else {
node *q = findPosition(root, x);
if (q->x > x) {
q->left = createNode(x);
} else {
q->right = createNode(x);
}
}
}
Tính độ cao của cây nhị phân tìm kiếm:
/* Compute the "height" of a tree -- the number of
nodes along the longest path from the root node
down to the farthest leaf node.*/
int height(node *root) {
if (root == NULL) {
return 0;
} else {
/* compute the height of each subtree */
int lHeight = height(root->left);
int rHeight = height(root->right);
/* use the larger one */
if (lHeight > rHeight) {
return (lHeight + 1);
} else {
return (rHeight + 1);
}
}
}
Tôi viết tiếp một hàm in ra cây nhị phân dưới dạng cây thư mục để chúng ta có thể quan sát trực quan nhất cây nhị phân. Về bản chất, đây chính là cách duyệt NLR (Node-Left-Right). Có 6 cách duyệt trên cây nhị phân: NLR , LNR, LRN, NRL, RNL, RLN.
// print out the binary search tree graphically
bool rec[10];
void printTree(node* root, int depth) {
if (root == NULL) {
return;
}
cout << " ";
for (int i = 0; i < depth; i++) {
if (i == depth - 1) {
if (rec[depth - 1]) {
setColor(160);
cout << "L";
setColor(15);
} else {
setColor(48);
cout << "R";
setColor(15);
}
cout << "------->";
} else {
if (rec[i]) {
cout << "| ";
} else {
cout << " ";
}
}
}
setColor(207);
cout << " " << root->x << " " << endl;
setColor(15);
rec[depth] = true;
printTree(root->left, depth + 1);
rec[depth] = false;
printTree(root->right, depth + 1);
}
Giờ chạy thử chương trình xem chúng ta được gì nhé (các nút được tô màu đỏ, L là nhánh trái, R là nhánh phải).
Yeah, đây là kết quả được in ra console, hơi màu mè xíu LOL.
Hãy thử so sánh với hình minh họa ở đầu bài để xem code của chúng ta hoạt động chính xác không nhé.
Loading...