intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

Bài giảng Cấu trúc dữ liệu - Bài 5: Cấu trúc cây

Chia sẻ: Trần Ngọc Lâm | Ngày: | Loại File: PPT | Số trang:102

Thêm vào BST
Báo xấu
131
lượt xem 12
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài giảng Cấu trúc dữ liệu bài 5: Cấu trúc cây trình bày nội dung cấu trúc cây, cây nhị phân, cây nhị phân tìm kiếm, cây nhị phân tìm kiếm cân bằng AVL, phần mở rộng (cây n-phân),... Tham khảo bài giảng náy để nắm bắt chi tiết môn học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cấu trúc dữ liệu - Bài 5: Cấu trúc cây

  1. Tree Structure 2008 1
  2. Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL  Phần mở rộng (cây n-phân)  Cây Top-Down  B-Tree 2008 2
  3. Cấu trúc dữ liệu 2008 3
  4. Cấu trúc cây  Tập hợp các nút và cạnh nối các nút đó  Có một nút gọi là gốc  Quan hệ one-to-many giữa các nút  Có duy nhất một đường đi từ gốc đến một nút  Các loại cây:  Nhị phân: mỗi nút có {0,1, 2} nút con  Tam phân: mỗi nút có {0,1,2,3} nút con  n-phân: mỗi nút có {0,1,..,n} nút con 2008 4
  5. Cấu trúc cây Sao trong máy tính, cây lại thể hiện ngược? 2008 5
  6. Khái niệm J gốc Cạnh nút Z A B R D Q K A F L Lá 2008 6
  7. Khái niệm  Thuật ngữ  Nút gốc: không có nút cha  Nút lá: không có nút con  Nút trong: không phải nút con và nút gốc  Chiều cao: khoảng cách từ gốc đến lá Nút gốc Nút trong Chiều cao Nút lá 2008 7
  8. Khái niệm Root Node A Node B Node C Node D Node E Node F Node G Node H Node I Node J Node K Node L Cây con Nút anh em 2008 8
  9. Nội dung  Cấu trúc cây  Cây nhị phân  Cây nhị phân tìm kiếm  Cây nhị phân tìm kiếm cân bằng AVL 2008 9
  10. Binary Tree  Cấu trúc cây đơn giản nhất  Tại mỗi nút gồm các 3 thành phần  Phần data: chứa giá trị, thông tin…  Liên kết đến nút con trái (nếu có)  Liên kết đến nút con phải (nếu có)  Cây nhị phân có thể rỗng (ko có nút nào)  Cây NP khác rỗng có 1 nút gốc  Có duy nhất 1 đường đi từ gốc đến 1 nút  Nút không có nút con bên trái và con bên phải là nút lá 2008 10
  11. Binary Tree Kích thước = 9 (số nút) Mức 0 A Cây con trái Cây con phải Mức 1 B C Mức 2 D E F G Mức 3 H I Độ sâu/chiều cao = 3 2008 11
  12. Binary Tree  Cây nhị phân đúng:  Nút gốc và nút trung gian có đúng 2 con  Cây nhị phân đúng có n nút lá thì số nút trên cây 2n-1 A B C D E F G H I J K 2008 12
  13. Binary Tree  Cây nhị phân đầy đủ với chiều sâu d  Phải là cây nhị phân đúng  Tất cả nút lá có chiều sâu d A Số nút = (2 -1) d+1 Số nút trung gian = ? Biết số nút tính d của cây NP đầy đủ B C D E F G 2008 13
  14. Binary Tree  Duyệt cây:  Do cây là cấu trúc ko tuyến tính  3 cách duyệt cây NP  Duyệt theo thứ tự trước PreOrder: NLR  Duyệt theo thứ tự giữa InOrder: LNR  Duyệt theo thứ tự sau PostOrder: LRN 2008 14
  15. Binary Tree A PreOrder: InOrder: B C PostOrder: D E F G H I J K 2008 15
  16. Binary Tree  Cài đặt cây NP dùng liên kết typedef struct node Chứa thông tin của nút { DataType info; struct node * left; Cấu trúc của một nút struct node * right; Trỏ đến nút con phải } NODE; typedef NODE * NodePtr; Trỏ đến nút con trái NodePtr pTree; Trỏ nút gốc của cây NP 2008 16
  17. Binary Tree pTree Con trỏ pTree trỏ 8 đến nút gốc của cây 5 10 1 3 4 20 9 7 2008 17
  18. Binary Tree  Các thao tác:  NewNode, CreateNode, FreeNode, Init, IsEmpty  InsertLeft, InsertRight  DeleteLeft, DeleteRight  PreOrder, InOrder, PostOrder Phần minh  Search hoạ dùng  ClearTree DataType là kiểu int 2008 18
  19. Binary Tree  CreateNode: tạo một nút mới có giá trị là x Crea NodePtr CreateNode(int x) node { NodePtr node; node = NewNode(); new node->info = x; X node->left = NULL; node->right = NULL; return node; } 2008 19
  20. Binary Tree  InsertLeft: thêm nút con bên trái nút p int InsertLeft(NodePtr p, int x) { if (p == NULL) return FALSE; if (p->left != NULL) return FALSE; p->left = CreateNode(x); return TRUE; } 2008 20
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2