Cấu trúc dữ liệu cây

Bài viết Cấu trúc dữ liệu cây thuộc chủ đề về HỎi Đáp Là Gì thời gian này đang được rất nhiều bạn quan tâm đúng không nào !! Hôm nay, Hãy cùng Moki.vn tìm hiểu Cấu trúc dữ liệu cây trong bài viết hôm nay nhé ! Các bạn đang xem bài viết : “Cấu trúc dữ liệu cây”

Đánh giá về Cấu trúc dữ liệu cây

Xem nhanh

Cấu trúc dữ liệu cây biểu diễn các nút (nút) được kết nối bởi các bên cạnh. Chúng ta sẽ tìm hiểu thông tin về Cây nhị phân (Cây nhị phân) và Cây tìm kiếm nhị phân (Cây tìm kiếm nhị phân) trong phần này.

Cây nhị phân là một cấu trúc dữ liệu đặc biệt được dùng cho mục đích lưu trữ dữ liệu. Một cây nhị phân có một điều kiện đặc biệt là mỗi nút có khả năng có tối đa hai nút con. Một cây nhị phân tận dụng lợi thế của hai kiểu cấu trúc dữ liệu: một mảng đã sắp thứ tự và một danh sách kết nối (Linked List), do đó việc tìm kiếm sẽ nhanh như trong mảng đã sắp thứ tự và các thao tác chèn và xóa cũng sẽ nhénh bằng trong Linked List.

Các khái niệm cơ bản về cây nhị phân

Dưới đây là một số khái niệm quan trọng liên quan tới cây nhị phân:

• Đường: là một dãy các nút cùng với các cạnh của một cây.
• Nút gốc (Root): nút trên cùng của cây được gọi là nút gốc. Một cây sẽ chỉ có một nút gốc và một đường xuất phát từ nút gốc tới bất kỳ nút nào khác. Nút gốc là nút duy nhất không có bất kỳ nút cha nào.
• Nút cha: bất kỳ nút nào ngoại trừ nút gốc mà có một cạnh hướng lên một nút khác thì được gọi là nút cha.
• Nút con: nút ở dưới một nút đã cho được liên kết bởi cạnh dưới của nó được gọi là nút con của nút đó.
• Nút lá: nút mà không có bất kỳ nút con nào thì được gọi là nút lá.
• Cây con: cây con biểu diễn các con của một nút.
• Truy cập: kiểm tra giá trị của một nút khi điều khiển là đang trên một nút đó.
• Duyệt: duyệt qua các nút theo một thứ tự nào đó.
• Bậc: 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, …
• Khóa (Key): biểu diễn một giá trị của một nút dựa trên những gì mà một thao tác tìm kiếm thực hiện trên nút.

Biểu diễn cây tìm kiếm nhị phân

Cây tìm kiếm nhị phân biểu diễn một hành vi đặc biệt. Con bên trái của một nút phải có giá trị nhỏ hơn giá trị của nút cha (của nút con này) và con bên phải của nút phải có giá trị lớn hơn giá trị của nút cha (của nút con này). Hình minh họa:

Chúng ta đang triển khai cây bởi dùng đối tượng nút và kết nối chúng thông qua các tham chiếu.

Nút (Node) trong cây tìm kiếm nhị phân

Một nút sẽ có cấu trúc như dưới đây. Nút có phần dữ liệu và phần tham chiếu tới các nút con bên trái và nút con bên phải.

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ùng một cấu trúc.

vận hành cơ bản trên cây tìm kiếm nhị phân

Dưới đây liệt kê các hoạt động cơ bản có khả năng được thực hiện trên cấu trúc dữ liệu cây tìm kiếm nhị phân:

• Chèn: chèn một phần tử vào trong một cây/ tạo một cây.
• Tìm kiếm: tìm kiếm một phần tử trong một cây.
• Duyệt tiền thứ tự: duyệt một cây theo hình thức duyệt tiền thứ tự (tham khảo chương sau).
• Duyệt trung thứ tự: duyệt một cây theo cách thức duyệt trung thứ tự (tham khảo chương sau).
• Duyệt hậu thứ tự: duyệt một cây theo hình thức duyệt hậu thứ tự (tham khảo chương sau).

Trong chương này, chúng ta sẽ tìm hiểu chi tiết cách tạo (chèn) cấu trúc cây và cách tìm kiếm một phần tử dữ liệu trên một cây. Chương sau chúng ta sẽ tìm hiểu chi tiết về các cách duyệt cây.

hoạt động chèn trong cây tìm kiếm nhị phân

Bước chèn đầu tiên sẽ tạo thành cây. Tiếp đó là sẽ chèn từng phần tử vào trong cây. Đầu tiên chúng ta cần xác định vị trí chính xác của nó. Bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn giá trị khóa, thì tìm kiếm vị trí rỗng trong cây con bên trái và chèn dữ liệu. Nếu không nhỏ hơn, tìm vị trí rỗng trong cây con bên phải và chèn dữ liệu. (Nếu bạn chưa hiểu, bạn có khả năng đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại chèn như vậy và xem hình minh họa)

Giải thuật cho vận hành chèn

If root là NULL thì tạo nút gốc (root node) return If root đã tồn tại thì sau đó so sánh dữ liệu với node.data while tới vị trí chèn đã xác định If dữ liệu là lớn hơn node.data tới cây con bên phải else tới cây con bên trái kết thúc while chèn dữ liệu Kết thúc If 

Giải thuật mẫu cho hoạt động chèn

Từ trên ta có khả năng suy ra giải thuật mẫu cho vận hành chèn trong cây tìm kiếm nhị phân như sau:

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; //Nếu cây là trống, chúng ta tạo root node if(root == NULL) root = tempNode; else current = root; parent = NULL; while(1) parent = current; //tới cây con bên trái if(data < parent->data) current = current->leftChild; //chèn dữ liệu vào bên trái if(current == NULL) parent->leftChild = tempNode; return; //tới cây con bên phải else current = current->rightChild; //chèn dữ liệu vào bên phải if(current == NULL) parent->rightChild = tempNode; return; 

Để tìm hiểu code đầy đủ của cấu trúc dữ liệu cây trong ngôn ngữ C, mời bạn click chuột vào chương: Duyệt cây trong C

vận hành tìm kiếm trong cây nhị phân

Mỗi khi một phần tử cần tìm kiếm: bắt đầu tìm kiếm từ nút gốc, sau đó nếu dữ liệu là nhỏ hơn tổng giá trị khóa, thì tìm kiếm phần tử trong cây con bên trái; nếu không nhỏ hơn thì tìm kiếm phần tử trong cây con bên phải. (Nếu bạn chưa hiểu, bạn có khả năng đọc lại phần Biểu diễn cây tìm kiếm nhị phân ở trên để biết tại sao lại tìm kiếm như vậy và xem hình minh họa)

Giải thuật cho vận hành tìm kiếm

If root.data là bằng với search.data return root else while không tìm thấy dữ liệu If data là lớn hơn node.data tới cây con bên phải else tới cây con bên trái If data được tìm thấy return node kết thúc while return không tìm thấy data Kết thúc if 

Giải thuật mẫu cho hoạt động tìm kiếm

Từ trên ta có thể suy ra giải thuật mẫu cho hoạt động tìm kiếm trong cây tìm kiếm nhị phân như sau:

struct node* search(int data) struct node *current = root; printf("Truy cap phan tu: "); while(current->data != data) if(current != NULL) printf("%d ",current->data); //tới cây con bên trái if(current->data > data) current = current->leftChild; //else tới cây con bên phải else current = current->rightChild; //không tìm thấy if(current == NULL) return NULL; return current; 

Ví dụ về duyệt cây trong C cấu trúc dữ liệu và giải thuật

#include <stdio.h> #include <stdlib.h> struct node int data; struct node *leftChild; struct node *rightChild; ; struct node *root = NULL; 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; //kiem tra neu cay la trong if(root == NULL) root = tempNode; else current = root; parent = NULL; while(1) parent = current; //chuyen toi cay con ben trai if(data < parent->data) current = current->leftChild; //chen du lieu vao cay con ben trai if(current == NULL) parent->leftChild = tempNode; return; //chuyen toi cay con ben phai else current = current->rightChild; //chen du lieu vao cay con ben phai if(current == NULL) parent->rightChild = tempNode; return; struct node* search(int data) struct node *current = root; printf("Truy cap cac phan tu cua cay: "); while(current->data != data) if(current != NULL) printf("%d ",current->data); //chuyen toi cay con ben trai if(current->data > data) current = current->leftChild; //chuyen toi cay con ben phai else current = current->rightChild; //khong tim thay if(current == NULL) return NULL; return current; void pre_order_traversal(struct node* root) if(root != NULL) printf("%d ",root->data); pre_order_traversal(root->leftChild); pre_order_traversal(root->rightChild); void inorder_traversal(struct node* root) if(root != NULL) inorder_traversal(root->leftChild); printf("%d ",root->data); inorder_traversal(root->rightChild); void post_order_traversal(struct node* root) if(root != NULL) post_order_traversal(root->leftChild); post_order_traversal(root->rightChild); printf("%d ", root->data); int main() int i; int array[7] = 27, 14, 35, 10, 19, 31, 42 ; for(i = 0; i < 7; i++) insert(array[i]); i = 31; struct node * temp = search(i); if(temp != NULL) printf("[%d] Da tim thay phan tu.", temp->data); printf("n"); else printf("[ x ] Khong tim thay phan tu (%d).n", i); i = 15; temp = search(i); if(temp != NULL) printf("[%d] Da tim thay phan tu.", temp->data); printf("n"); else printf("[ x ] Khong tim thay phan tu (%d).n", i); printf("nCach duyet tien thu tu: "); pre_order_traversal(root); printf("nCach duyet trung thu tu: "); inorder_traversal(root); printf("nCach duyet hau thu tu: "); post_order_traversal(root); return 0; 

Kết quả

Biên dịch và chạy chương trình C trên sẽ cho kết quả:

Các câu hỏi về cây ???c là gì

Nếu có bắt kỳ câu hỏi thắc mắt nào vê cây ???c là gì hãy cho chúng mình biết nhé, mõi thắt mắt hay góp ý của các bạn sẽ giúp mình cải thiện hơn trong các bài sau nhé <3 Bài viết cây ???c là gì ! được mình và team xem xét cũng như tổng hợp từ nhiều nguồn. Nếu thấy bài viết cây ???c là gì Cực hay ! Hay thì hãy ủng hộ team Like hoặc share. Nếu thấy bài viết cây ???c là gì rât hay ! chưa hay, hoặc cần bổ sung. Bạn góp ý giúp mình nhé!!

Các Hình Ảnh Về cây ???c là gì

Các hình ảnh về cây ???c là gì đang được chúng mình Cập nhập. Nếu các bạn mong muốn đóng góp, Hãy gửi mail về hộp thư [email protected] Nếu có bất kỳ đóng góp hay liên hệ. Hãy Mail ngay cho tụi mình nhé

Tham khảo kiến thức về cây ???c là gì tại WikiPedia

Bạn nên tra cứu thêm thông tin chi tiết về cây ???c là gì từ web Wikipedia tiếng Việt.◄ Tham Gia Cộng Đồng Tại

???? Nguồn Tin tại: https://moki.vn/

???? Xem Thêm Chủ Đề Liên Quan tại : https://moki.vn/la-gi/