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

Cấu trúc dữ liệu và giải thuật-Cây và cây nhị phân

Chia sẻ: Phan Thi Ngoc Giau | Ngày: | Loại File: PDF | Số trang:14

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

Cây là một tập hợp T các phần tử (gọi là nút của cây), trong đó có một nút đặc biệt gọi là nút gốc, các nút còn lại được chia thành những tập rời nhau T1, T2, …,Tn theo quan hệ phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta gọi là quan hệ cha – con.

Chủ đề:

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

Lưu

Nội dung Text: Cấu trúc dữ liệu và giải thuật-Cây và cây nhị phân

  1. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. NỘI DUNG Click To Edit Master Title Style Cấu trúc dữ liệu 1 vá thuật giải CÂY VÀ CÂY NHỊ PHÂN CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 1
  2. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Định Nghĩa Cây  Cây là một tập hợp T các phần tử (gọi là nút của cây), trong đó có một nút đặc biệt gọi là nút gốc, các nút còn lại được chia thành Cấu trúc dữ liệu 1 vá thuật giải những tập rời nhau T1, T2, …,Tn theo quan hệ CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 phân cấp, trong đó Ti cũng là 1 cây. Mỗi nút ở cấp i sẽ quản lý một số nút ở cấp i+1. Quan hệ này người ta gọi là quan hệ cha – con. 2
  3. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Một Số Khái Niệm • Bậc của một nút: là số cây con của nút đó . • Bậc của một cây: là bậc lớn nhất của các nút trong cây • Nút gốc: là nút không có nút cha. • Nút lá: là nút có bậc bằng 0 . Cấu trúc dữ liệu 1 vá thuật giải • Mức của một nút: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 – Mức (gốc (T) ) = 0. – Gọi T1, T2, T3, ... , Tn là các cây con của T0 : Mức (T1) = Mức (T2) = . . . = Mức (Tn) = Mức (T0) + 1. • Độ dài đường đi từ gốc đến nút x: là số nhánh cần đi qua kể từ gốc đến x. 3
  4. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Ví Dụ 1 Tổ Chức Dạng Cây BB-Electronic Corp. R&D Kinh doanh Taøi vuï Saûn xuaát Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Noäi ñòa Quoác teá TV CD Amplier Chaâu Myõ Caùc aâu nöôùc 4
  5. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Cây Nhị PhânEdit Click To Master Title Style • Mỗi nút có tối đa 2 cây con Caây Caây con con Cấu trúc dữ liệu 1 vá thuật giải traùi phaûi CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 5
  6. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Một Số Tính Chất Của Cây Nhị Phân • Số nút nằm ở mức i  2i. • Số nút lá  2h-1, với h là chiều cao của cây. • Chiều cao của cây h  Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 log2(N) – N = số nút trong cây • Số nút trong cây  2h- 1. 6
  7. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Cấu Trúc To Liệu Của Cây Nhị Phân Click Dữ Edit Master Title Style typedef struct tagTNode { Data Key; struct tagTNode *pLeft; Key struct tagTNode *pRight; }TNode; Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 typedef TNode *TREE; 7
  8. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Ví Dụ Cây Được Tổ Chức Trong Bộ Nhớ Click To Edit Master Title Style Trong 1f 2f 6 3f 3f Cấu trúc dữ liệu 1 vá thuật giải 2f CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 7f 9 N N 4 5f 5f 7f N 5 N N 8 N 8
  9. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Duyệt Cây Nhị Phân  Có 3 trình tự thăm gốc :  Duyệt trước  Duyệt giữa  Duyệt sau Cấu trúc dữ liệu 1 vá thuật giải  Độ phức tạp O (log2(h)) CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 Trong đó h là chiều cao cây 9
  10. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Ví Dụ Kết To Edit Master Title Style Click Quả Của Phép Duyệt Cây 9 8 2 1 6 5 7 Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 10 3 12 4 • NLR: 9, 2, 6, 1, 10, 8, 5, 3, 7, 12, 4. • LNR: 6, 2, 10, 1, 9, 3, 5, 8, 12, 7, 4. • Kết quả của phép duyệt : LRN, NRL,LRN, LNR? 10
  11. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Duyệt Trước void NLR(TREE Root) { if (Root != NULL) { ; //Xử lý tương ứng theo nhu cầu Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 NLR(Root->pLeft); NLR(Root->pRight); } } 11
  12. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Duyệt Giữa void LNR(TREE Root) { if (Root != NULL) { LNR(Root->pLeft); Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 ; // Xử lý tương ứng theo nhu cầu LNR(Root->pRight); } } 12
  13. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Click To Edit Master Title Style Duyệt Sau void LRN(TREE Root) { if (Root != NULL) { LRN(Root->pLeft); Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 LRN(Root->pRight); ; // Xử lý tương ứng theo nhu cầu } } 13
  14. Generated by Foxit PDF Creator © Foxit Software http://www.foxitsoftware.com For evaluation only. Biểu Diễn Cây Tổng Quát Bằng Title Style Click To Edit Master Cây Nhị Phân A B E C A Cấu trúc dữ liệu 1 vá thuật giải CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 H D F B C D G I J E F G H I J 14
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