Cây đại diện cho các nút được kết nối bởi các cạnh. Chúng tôi sẽ thảo luận cụ thể về cây nhị phân hoặc cây tìm kiếm nhị phân.
Cây nhị phân là một cơ sở hạ tầng đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai con. Cây nhị phân có các lợi ích của cả mảng được sắp xếp và danh sách được liên kết vì tìm kiếm nhanh như trong mảng được sắp xếp và thao tác chèn hoặc xóa cũng nhanh như trong danh sách được liên kết.
Điều khoản quan trọng
Sau đây là các điều khoản quan trọng đối với cây.
- Đường dẫn - Đường dẫn đề cập đến chuỗi các nút dọc theo các cạnh của cây.
- Root - Nút ở đầu cây được gọi là root. Chỉ có một gốc trên mỗi cây và một đường dẫn từ nút gốc đến bất kỳ nút nào.
- Cha mẹ - Bất kỳ nút nào ngoại trừ nút gốc có một cạnh hướng lên một nút được gọi là cha.
- Con - Nút bên dưới một nút đã cho được nối với cạnh xuống của nó được gọi là nút con của nó.
- Lá - Nút không có nút con nào được gọi là nút lá.
- Subtree - Subtree đại diện cho hậu duệ của một nút.
- Tham quan - Tham quan nghĩa là kiểm tra giá trị của nút khi điều khiển nằm trên nút.
- Traversing - Traversing có nghĩa là đi qua các nút theo một thứ tự cụ thể.
- Cấp độ - Cấp độ của một nút đại diện cho việc tạo ra một nút. Nếu nút gốc ở mức 0, thì nút con tiếp theo của nó ở cấp 1, cháu của nó ở cấp 2, v.v.
- khóa - Khóa biểu thị giá trị của một nút dựa trên đó thao tác tìm kiếm sẽ được thực hiện cho một nút.
Đại diện cây tìm kiếm nhị phân
Cây tìm kiếm nhị phân thể hiện một hành vi đặc biệt. Con trái của một nút phải có giá trị nhỏ hơn giá trị của cha mẹ và con phải của nút phải có giá trị lớn hơn giá trị cha của nó.
Chúng ta sẽ thực hiện cây bằng cách sử dụng đối tượng nút và kết nối chúng thông qua các tham chiếu.
Nút cây
Mã để viết một nút cây sẽ tương tự như những gì được đưa ra dưới đây. Nó có một phần dữ liệu và tham chiếu đến các nút con trái và phải của nó.
struct node {
int data;
struct node *leftChild;
struct node *rightChild;
};
Trong một cây, tất cả các nút chia sẻ cấu trúc chung.
BST hoạt động cơ bản
Các hoạt động cơ bản có thể được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân, như sau -
- Chèn - Chèn một phần tử trong cây / tạo cây.
- Tìm kiếm - Tìm kiếm một phần tử trong cây.
- Preorder Traversal - Đi qua một cái cây theo cách đặt hàng trước.
- Inorder Traversal - Đi ngang qua một cái cây theo thứ tự.
- Postorder Traversal - Đi qua một cái cây theo cách đặt hàng sau.
Chúng ta sẽ học cách tạo (chèn vào) cấu trúc cây và tìm kiếm một mục dữ liệu trong cây trong chương này. Chúng ta sẽ tìm hiểu về các phương pháp đi ngang qua cây trong chương tới.
Chèn hoạt động
Việc chèn đầu tiên tạo ra cây. Sau đó, bất cứ khi nào một yếu tố được chèn vào, trước tiên hãy xác định vị trí thích hợp của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm vị trí trống trong cây con bên trái và chèn dữ liệu. Nếu không, tìm kiếm vị trí trống trong cây con bên phải và chèn dữ liệu.
Thuật toán
If root is NULL
then create root node
return
If root exists then
compare the data with node.data
while until insertion position is located
If data is greater than node.data
goto right subtree
else
goto left subtree
endwhile
insert data
end If
Thực hiện
Việc thực hiện chức năng chèn sẽ như thế này -
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty, create root node
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}
//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Hoạt động tìm kiếm
Bất cứ khi nào một phần tử được tìm kiếm, hãy bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu nhỏ hơn giá trị khóa, hãy tìm kiếm phần tử trong cây con bên trái. Nếu không, tìm kiếm phần tử trong cây con bên phải. Thực hiện theo cùng một thuật toán cho mỗi nút.
Thuật toán
If root.data is equal to search.data
return root
else
while data not found
If data is greater than node.data
goto right subtree
else
goto left subtree
If data found
return node
endwhile
return data not found
end if
Việc thực hiện thuật toán này sẽ giống như thế này.
struct node* search(int data) {
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data) {
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data) {
current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL) {
return NULL;
}
return current;
}
}
Được cập nhật: 25 tháng 3 lúc 13:12:19 | Lượt xem: 388