Bài giảng Cấu trúc dữ liệu và giải thuật 1 - Chương 6: Cây và cây nhị phân

NỘI DUNGCÂY VÀ CÂY NHỊ PHÂNĐịnh Nghĩa CâyCâ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.Một Số Khái NiệmBậ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 .Mức của một nút: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.Ví Dụ 1 Tổ Chức Dạng CâyBB-Electronic Corp.R&DKinh doanhTaøi vuïSaûn xuaátTVCDAmplierNoäi ñòaQuoác teáChaâu aâuMyõCaùc nöôùcCây Nhị PhânMỗi nút có tối đa 2 cây conCaây con traùiCaây con phaûiMột Số Tính Chất Của Cây Nhị PhânSố 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  log2(N)N = số nút trong câySố nút trong cây  2h-1.Cấu Trúc Dữ Liệu Của Cây Nhị Phântypedef struct tagTNode{ Data Key; struct tagTNode *pLeft; struct tagTNode *pRight; }TNode;typedef TNode *TREE;KeyVí Dụ Cây Được Tổ Chức Trong Bộ Nhớ Trong3f62f1fN97f3f5f4N2fN5N5fN8N7fDuyệ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 Độ phức tạp O (log2(h)) Trong đó h là chiều cao câyVí Dụ Kết Quả Của Phép Duyệt CâyNLR: 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?9821610537412Duyệt Trước void NLR(TREE Root){ if (Root != NULL) { ; //Xử lý tương ứng theo nhu cầu NLR(Root->pLeft); NLR(Root->pRight); }}Duyệt Giữavoid LNR(TREE Root){ if (Root != NULL) { LNR(Root->pLeft); ; // Xử lý tương ứng theo nhu cầu LNR(Root->pRight); }}Duyệt Sauvoid LRN(TREE Root){ if (Root != NULL) { LRN(Root->pLeft); LRN(Root->pRight); ; // Xử lý tương ứng theo nhu cầu }}Biểu Diễn Cây Tổng Quát Bằng Cây Nhị PhânABCDEFGHIJABCDEFGHIJ