tailieunhanh - TOÁN RỜI RẠC - CÂY – PHẦN 4

Định nghĩa: Trong nhiều trường hợp, ta cần phải “điểm danh” hay “thăm” một cách có hệ thống mọi đỉnh của một cây nhị phân, mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt cây nhị phân hay đọc cây nhị phân. Có nhiều thuật toán duyệt cây nhị phân, các thuật toán đó khác nhau chủ yếu ở thứ tự thăm các đỉnh. Cây nhị phân T có gốc r được ký hiệu là T(r). Giả sử r có con bên trái là u, con bên phải là v. Cây có gốc u và các đỉnh khác. | TOÁN RỜI RẠC - CÂY - PHẦN 4 DUYỆT CÂY NHỊ PHÂN . Định nghĩa Trong nhiều trường hợp ta cần phải điểm danh hay thăm một cách có hệ thống mọi đỉnh của một cây nhị phân mỗi đỉnh chỉ một lần. Ta gọi đó là việc duyệt cây nhị phân hay đọc cây nhị phân. Có nhiều thuật toán duyệt cây nhị phân các thuật toán đó khác nhau chủ yếu ở thứ tự thăm các đỉnh. Cây nhị phân T có gốc r được ký hiệu là T r . Giả sử r có con bên trái là u con bên phải là v. Cây có gốc u và các đỉnh khác là mọi dòng dõi của u trong T gọi là cây con bên trái của T ký hiệu T u . Tương tự ta có cây con bên phải T v của T. Một cây T r có thể không có cây con bên trái hay bên phải. Sau đây là ba trong các thuật toán duyệt cây nhị phân T r . Các thuật toán đều được trình bày đệ quy. Chú ý rằng khi cây T x chỉ là môt đỉnh x thì duyệt T x có nghĩa là thăm đỉnh x . Thí dụ 5 . Các thuật toán duyệt cây nhị phân 1 Thuật toán tiền thứ tự 1. Thăm gốc r. 2. Duyệt cây con bên trái của T r theo tiền thứ tự. 3. Duyệt cây con bên phải của T r theo tiền thứ tự. Duyệt cây nhị phân T a trong hình trên theo tiền thứ tự 1. Thăm a 2. Duyệt T b . Thăm b . Duyệt T d . Thăm d . Duyệt T g . Thăm g . Duyệt T l Thăm l . Duyệt T h Thăm h . Duyệt T e . Thăm e . Duyệt T i . Thăm i . Duyệt T m Thăm m . Duyệt T n Thăm n 3. Duyệt T c

• Toán học
• toán cao cấp
• tài liệu toán cao cấp
• giáo trình toán cao cấp
• lý thuyết toán cao cấp
• tự học toán cao cấp
• Bài giảng toán cao cấp
• Bài tập toán cao cấp
• Đề thi toán cao cấp
• Toán cao cấp C2
• Toán cao cấp A1
• Toán cao cấp C
• Toán cao cấp A3
• Toán cao cấp A2
• Toán cao cấp C1
• Toán cao cấp B1
• Toán cap cấp A2
• ôn thi toán cao cấp
• giải toán cao cấp
• cách làm bài thi toán cao cấp
• câu hỏi toán cao cấp
• luyện tập toán cao cấp
• Bài tập trắc nghiệm toán cao cấp
• Ôn tập toán cao cấp
• Bài tâp toán cao cấp
• Trắc nghiệm toán cao cấp
• Toán cao cấp về giới hạn
• Bài tập Toán cao cấp A1
• Đề thi Toán cao cấp A1