Kiến trúc máy tính - Bài 10

Chia sẻ: Lê Trung Thống | Ngày: | Loại File: PPT | Số trang:41

Thêm vào BST

Báo xấu

86
lượt xem 9
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Cây Tree .Cây – Cấu trúc dữ liệu phi tuyến (TreesNonlinear data structures) ĐHGTVT CNTT KTVT CT 2 .Một số ví dụ sử dụng cấu

Chủ đề:

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

Lưu

Nội dung Text: Kiến trúc máy tính - Bài 10

Bài 10. Cây Tree 1
Cây – Cấu trúc dữ liệu phi tuyến (TreesNonlinear data structures) ĐHGTVT CT CNTT KTVT 2
Một số ví dụ sử dụng cấu trúc dữ liệu cây 3 Data structures trees
Cây gia phả 4 Data structures trees
Cây biểu diễn các tổ chức ĐHGTVT KT ĐĐT CNTT CK … KTVT ĐKH TTBĐ CNPM KHMT VT Mạng 5 Data structures trees
Cây biểu diễn hệ thống files Cây mô tả sự phân chia hệ thống files 6 Data structures trees
Cấu trúc của cuốn Cây thể hiện cấu trúc sách thông tin Cây thể hiện cấu trúc của một cuốn sách 7 Data structures trees
Cây thể hiện lựa Cây quyết định chọn quyết định Bạn đã có gia đình riêng chưa? rồi chưa Bạn có bằng đại học không? Không chấp nhận có Không Bạn có tốt nghiệp loại giỏi không? Không chấp nhận có không Chấp nhận Không chấp nhận Cây quyết định tuyển nhân viên 8 Data structures trees
Cây nhị phân biểu diễn các biểu thức toán học Một cây nhị phân biểu diễn một biểu thức. Cây này biểu diễn biểu thức ((((3+1)*3/((95)+2))((3*(74))+6)). Gi á trị được kết hợp lại tại nút trong có nhãn “/” là 2. 9 Data structures trees
Cây cú pháp S  XY X  XA | a | b Y  AY | a A  a 10 Data structures trees
Tổng kết: Cây là cách tổ chức dữ liệu rất hữu dụng trong rất nhiều ứng dụng khác nhau ĐHGTVT CT CNTT KTVT 11 Data structures trees
Cây tổng quát Cây là gì? Cây là một tập các nút với quan hệ chacon (parentchild) giữa các nút. Trong đó có một nút được gọi là gốc và nó không có cha. Trong khoa học máy tính, một cây là một mô hình trừu tượng của cấu trúc phân cấp. Các ứng dụng: Tổ chức biểu đồ  Hệ thống file  Các môi trường lập trình …  12 Data structures trees
Một số khái niệm Gốc (root): gốc là nút không Cây con: Cây bao gồm có nút cha ( vd: A) một số nút của một cây ban đầu Nút trong: Nút có ít nhất một nút con (Vd: A, B, C, F) A Nút ngoài (lá): nút không có nút con (Vd: E, I, J, K, G, H, D) B C D Đô sâu của một nút: Nút gốc có độ sâu là 0, nếu E F G H nút cha có độ sâu là h thì nút con có độ sâu là h+1 Chiều cao của cây: là giá trị I J K lớn nhất của độ sâu của tất cả các nút (3) Cây con 13 Data structures trees
Cấu trúc dữ liệu trừu tượng cây Chúng ta quản lý các nút Các phương thức truy vấn: thông qua địa chỉ của int isInternal(Node*) chúng.  int isExternal(Node*) Các phương thức chung:  int isRoot(Node*) int size()   int isEmpty() Thêm vào đó là những phương  Các phương duyệt cây: thức cập nhật được định nghĩa void preorder(Node*) trong các cấu trúc dữ liệu tạo  void inorder(Node*) Tree ADT (Node tạo cây)  void postorder(Node*)  Phương thức thêm phần tử vào Các phương thức truy cập: cây. Địa chỉ root()   void insert(Node* parent, Element e) ◊ Phương thức xóa phần tử  void remove(Node*); 14 Data structures trees
Duyêt theo thứ tự trước –preorder traversal Duyệt cây là cách đi thăm các nút của cây theo một Algorithm preOrder(v) hệ thống If(v!=null) Duyệt theo thứ tự trước, tức visit(v) là: nút cha được thăm trước for mỗi nút con w của v sau đó thăm các nút con, cháu, … preorder (w) 1 ĐHGTVT 10 2 6 CNTT CK QLGĐ 9 5 7 8 3 4 KHMT NHIET KHMT CNPM ĐMTX CKOT 15 Data structures trees
Ví dụ: Duyêt theo thứ tự trước Thăm cây theo thứ tự trước (preorder). Trong đó cây con được thăm theo thứ tự từ trái qua phải 16 Data structures trees
Bài tập: Hãy chỉ ra thứ tự thăm các nút của cây dưới đây bằng cách sử dụng phương pháp duyệt theo thứ tự trước? 17 Data structures trees
Thư tự thăm các nút bằng phương pháp duyệt theo thứ tự trước 18 Data structures trees
Duyệt theo thứ tự giữa inorder Traversal Algorithm inOrder(v) Duyệt theo thứ tự sau, tức là: If(v!=null) nút con được thăm trước sau đó thăm nút cha w = con cả của v inOrder(w) Ứng dụng: Tính toán không gian sử dụng bởi các files và visit(v) các thư mục con for mỗi nút con w1#w của v 4 cs16/ inOrder (w1) 9 2 6 todo.txt homeworks/ programs/ 1K 5 7 8 1 3 Robot.java h1c.doc h1nc.doc DDR.java Stocks.java 20K 3K 2K 10K 25K 19 Data structures trees
Duyệt theo thứ tự sau PostOrder Traversal Duyệt theo thứ tự sau, tức là: Algorithm postOrder(v) nút con được thăm trước sau đó thăm nút cha If(v!=null) Ứng dụng: Tính toán không for mỗi nút con w của v gian sử dụng bởi các files và các thư mục con postOrder (w) visit(v) 9 cs16/ 8 3 7 todo.txt homeworks/ programs/ 1K 4 5 6 1 2 Robot.java h1c.doc h1nc.doc DDR.java Stocks.java 20K 3K 2K 10K 25K 20 Data structures trees