cau

A. CÁC KHÁI NIỆM CƠ BẢN

Định nghĩa : Cây (tree): một tập hợp hữu hạn các phần tử gọi là các nút (nodes) và tập hợp hữu hạn các cạnh nối các cặp nút lại với nhau mà không tạo thành chu trình. Nói cách khác, cây là 1 đồ thị không có chu trình.

_ Ví dụ :

+ Bậc của nút là số cây con của nút đó ==> (Bậc nút I là 3) ; + Bậc của cây là bậc lơn nhất trong các nút ==> (Bậc của cây là 5) –-> Cây ngũ phân

+ Nút gốc : Không có cha (A) . Nút lá : Không có con (G, M, Q). Nút trung gian : Nút không phải là lá ; + Nút tiền bối(descendant) & nút hậu duệ (ancestor)

+ Độ dài đường đi = Số nút – 1. (A-D-I-O-Q : 5-1=4)

+ Chiều cao : từ nút đó đến nút lá xa nhất (D là 3). Chiều cao của cây là chiều cao của nút gốc (Cây là 4)

+ Độ sâu = Mức : Nút gốc đến nút đó (E là 1, M, N, O, P là 3)

Nhãn của một nút không phải là tên mà là giá trị được lưu trữ tại nút đó. Rừng là một tập hợp nhiều cây.

_ Có 3 phương pháp duyệt tổng quát: •tiền tự (preorder) •trung tự (inorder) •hậu tự (postorder)

B. CÁC PHÉP TOÁN CƠ BẢN TRÊN CÂY

C. DUYỆT CÂY NHỊ PHÂN

_ Các biểu thức duyệt: (N:Node, R:Right, L:Left)
………………….+ Tiền tự (NLR): duyệt nút gốc, duyệt tiền tựcon trái, duyệt tiền tự con phải. (PreOrder)
………………….+  Trung tự (LNR): duyệt trung tự con trái, duyệt nút gốc, duyệt trung tự con phải. (InOrder)
………………….+ Hậu tự (LRN): duyệt hậu tự con trái, duyệt hậu tự con phải, duyệt nút gốc. (PosOrder)
D.  CÂY TÌM KIẾM NHỊ PHÂN (BINARY SEARCH TREE-BST)
_ Không có 2 nút khóa trung nhau.
_ Duyệt trung tự tạo thành dãy các  nhãn tăng.
_ Quy ước : Cây rỗng là cây TKNP
_ Xóa nút cây :
E. KIẾN THỨC BỔ SUNG