tailieunhanh - Cây nhị phân
Cây nhị phân: là cây mà mỗi nút có tối đa 2 cây con Cây nhị phân tìm kiếm : là cây nhị phân trong đó tại mỗi nút, khóa của nút đang xét lớn hơn khóa của tất cả các nút thuộc cây con trái và nhỏ hơn tất cả các nút thuộc cây con phải. | CÂY NHỊ PHÂN TMT CÁC KHÁI NIỆM 1. Cấu trúc cây nhị phân 2. Các loại cây nhị phân a/ Cây nhị phân đúng (Strictly Binary Tree): Tất cả các nút đều có đúng hai con (ngoại trừ nút lá). CÁC KHÁI NIỆM b/ Cây nhị phân đầy (Complete Binary Tree): là cây nhị phân đúng và tất cả các nút lá ở cùng mức. ĐẶC ĐIỂM CÂY NHỊ PHÂN TÌM KIẾM Là cây nhị phân Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải Nút có giá trị nhỏ nhất nằm ở trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây 7 3 36 1 6 15 40 23 4 Cây nhị phân cân bằng (AVL): Một cây nhị phân được gọi là cây nhị phân cân bằng nếu và chỉ nếu đối với mọi nút của cây thì chiều cao của cây con bên trái và chiều cao của cây con bên phải hơn kém nhau nhiều nhất là 1 (Theo Adelson - Velski và Landis). Cây nhị phân cân bằng hoàn toàn: Một cây nhị phân được gọi là cây nhị phân cân bằng hoàn toàn nếu và chỉ nếu đối với mọi nút của cây thì số nút . | CÂY NHỊ PHÂN TMT CÁC KHÁI NIỆM 1. Cấu trúc cây nhị phân 2. Các loại cây nhị phân a/ Cây nhị phân đúng (Strictly Binary Tree): Tất cả các nút đều có đúng hai con (ngoại trừ nút lá). CÁC KHÁI NIỆM b/ Cây nhị phân đầy (Complete Binary Tree): là cây nhị phân đúng và tất cả các nút lá ở cùng mức. ĐẶC ĐIỂM CÂY NHỊ PHÂN TÌM KIẾM Là cây nhị phân Giá trị của một node bất kỳ luôn lớn hơn giá trị của tất cả các node bên trái và nhỏ hơn giá trị tất cả các node bên phải Nút có giá trị nhỏ nhất nằm ở trái nhất của cây Nút có giá trị lớn nhất nằm ở phải nhất của cây 7 3 36 1 6 15 40 23 4 Cây nhị phân cân bằng (AVL): Một cây nhị phân được gọi là cây nhị phân cân bằng nếu và chỉ nếu đối với mọi nút của cây thì chiều cao của cây con bên trái và chiều cao của cây con bên phải hơn kém nhau nhiều nhất là 1 (Theo Adelson - Velski và Landis). Cây nhị phân cân bằng hoàn toàn: Một cây nhị phân được gọi là cây nhị phân cân bằng hoàn toàn nếu và chỉ nếu đối với mọi nút của cây thì số nút của cây con bên trái và số nút của cây con bên phải hơn kém nhau nhiều nhất là 1 Nút ĐỊNH NGHĨA KIỂU DỮ LIỆU typedef struct Node { Key; struct Node *Left, *Right; } *Tree; Giá trị Trỏ trái Trỏ phải TNODE Key pLeft pRight KHAI BÁO CÂY NHỊ typedef struct Node { int Key; struct Node *Left, *Right; } *Tree; XÂY DỰNG CÂY Ví dụ: có dãy số 20, 70, 30, 25, 35, 50, 80, 40, 60, 10 (3 trường hợp gốc là 50, gốc là, 10 hay gốc là 80) Ví dụ: có dãy số 20, 70, 30, 25, 35, 50, 80, 40, 60, 10 Ví dụ: có dãy số 20, 70, 30, 25, 35, 50, 80, 40, 60, 10 DUYỆT CÂY Thứ tự trước (NLR) Thứ tự giữa (LNR) Thứ tự sau (LRN) NLR 7 L7 R7 7 3 L3 R3 36 L36 R36 7 3 1 6 L6 36 15 R15 40 7 3 1 6 4 36 15 23 40 7 3 36 1 6 15 40 23 4 NLR Tại node t đang xét, nếu khác rỗng thì . In giá trị của t . Duyệt cây con bên trái của t theo thứ tự NLR . Duyệt cây con bên phải của t theo thứ tự NLR void NLR (TREE t) { if(t!=NULL) { coutKeypLeft); NLR(t->pRight); } } LNR L7 7 R7 L3 3 R3 7 L36 36 R36 1 3 L6 6 7 15 R15 36 40 1 3 4 6 7 15 23 36 40 7 3 36 1 6 15 40 23 4 LNR Tại node t đang xét, nếu khác rỗng thì . Duyệt cây con bên trái của t theo thứ tự LNR . In giá trị của t . Duyệt cây con bên phải của t theo thứ tự LNR void LNR (TREE t) { if(t!=NULL) { LNR(t->pLeft); coutKeypRight); } } LRN L7 R7 7 L3 R3 3 L36 R36 36 7 1 L6 6 3 R15 15 40 36 7 1 4 6 3 23 15 40 36 7 7 3 36 1 6 15 40 23 4 LRN Tại node t đang xét, nếu khác rỗng thì . Duyệt cây con bên trái của t theo thứ tự LRN . Duyệt cây con bên phải của t theo thứ tự LRN . In giá trị của t void LRN (TREE t) { if(t!=NULL) { LRN(t->pLeft); LRN(t->pRight); coutKey
đang nạp các trang xem trước
