Giáo trình Cấu trúc dữ liệu và Thuật toán (Phần 2): Cây và các thuật ngữ chính

Giáo trình toán học về cấu trúc dữ liệu và thuật toán phần 2, biên soạn theo chương trình đào tạo chuẩn, hệ thống hóa kiến thức từ cơ bản đến nâng cao.

• Trường học: Trường Đại Học Công Nghệ Thông Tin
• Chuyên ngành: Cấu Trúc Dữ Liệu Và Thuật Toán
• Đề tài: Giáo Trình Cấu Trúc Dữ Liệu Và Thuật Toán Phần 2
• Loại tài liệu: Giáo Trình
• Năm xuất bản: 2023
• Địa điểm: Hồ Chí Minh

Mục lục chi tiết

• 1. ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM
• 1.1. Định nghĩa cây
• 1.1.1. Cấu trúc đệ quy của cây
• 1.1.2. Cây trong thực tế ứng dụng
• 1.1.2.1. Cây lịch thi đấu
• 1.1.2.2. Cây gia phả
• 1.1.2.3. Cây phân cấp quản lý hành chính
• 1.1.2.4. Cây thư mục
• 1.1.2.5. Cấu trúc của sách
• 1.1.2.6. Cây gia phả ngược (Ancestor Tree)
• 1.1.2.7. Cây phân hoạch tập hợp
• 1.2. Các thuật ngữ chính
• 1.2.1. Đường đi trên cây
• 1.2.2. Độ cao và độ sâu/mức
• 1.2.3. Bậc (Degree)
• 1.3. Cây có thứ tự (Ordered Tree)
• 1.3.1. Thứ tự của các nút
• 1.3.2. Xếp thứ tự các nút
• 1.3.3. Duyệt theo thứ tự trước (Preorder Traversal)
• 1.3.4. Duyệt theo thứ tự sau (Postorder Traversal)
• 1.3.5. Duyệt theo thứ tự giữa (Inorder Traversal)
• 1.4. Cây có nhãn (Labeled Tree)
• 1.4.1. Cây biểu thức (Expression Tree)
• 1.4.2. Xác định quan hệ hậu duệ
• 1.5. ADT Cây
• 1.5.1. Các phép toán cơ bản
• 1.5.2. Biểu diễn cây
• 1.5.2.1. Biểu diễn cây dùng mảng
• 1.5.2.2. Danh sách các con (Lists of Children)
• 1.5.2.3. Dùng con trái và em kế cận phải
• 2. CÂY NHỊ PHÂN
• 2.1. Định nghĩa và tính chất
• 2.1.1. Định nghĩa cây nhị phân
• 2.1.2. Tính chất của cây nhị phân
• 2.1.3. Cây nhị phân đầy đủ (Full binary tree)
• 2.1.4. Cây nhị phân hoàn chỉnh (Complete Binary Trees)
• 2.1.5. Cây nhị phân cân đối (Balanced binary tree)
• 2.2. Biểu diễn cây nhị phân
• 2.2.1. Biểu diễn sử dụng mảng
• 2.2.2. Biểu diễn cây nhị phân dùng con trỏ
• 2.3. Các phép toán cơ bản
• 2.3.1. Tạo một nút (MakeTreeNode)
• 2.3.2. Cài đặt hàm tính số nút và độ sâu của cây
• 2.3.3. Loại bỏ cây (freeTree)
• 2.3.4. Duyệt cây nhị phân

Tóm tắt

I. Tổng quan cấu trúc dữ liệu cây Nền tảng thuật toán phi tuyến

Trong lĩnh vực khoa học máy tính, cấu trúc dữ liệu và thuật toán là hai trụ cột không thể tách rời. Nếu các cấu trúc tuyến tính như danh sách liên kết hay mảng giúp tổ chức dữ liệu theo một trình tự, thì cấu trúc dữ liệu cây mở ra một chiều không gian mới cho việc lưu trữ và truy xuất thông tin phân cấp. Cây là một cấu trúc dữ liệu phi tuyến, bao gồm các nút (node) được kết nối bởi các cạnh. Một nút đặc biệt được gọi là gốc (root), và từ đó, các nút khác được phân nhánh tạo thành một hệ thống thứ bậc. Mỗi nút có thể có một hoặc nhiều nút con, nhưng mỗi nút (trừ gốc) chỉ có duy nhất một nút cha (parent). Các nút không có con được gọi là lá (leaf). Định nghĩa đệ quy của cây là một trong những khái niệm cốt lõi: một nút đơn lẻ là một cây, và một cây mới có thể được xây dựng bằng cách kết nối một nút gốc với các cây con. Cấu trúc này mô phỏng hoàn hảo nhiều hệ thống trong thế giới thực, từ cây gia phả, sơ đồ tổ chức của một công ty, hệ thống tệp trong máy tính, cho đến cây lịch thi đấu thể thao. Việc hiểu rõ bản chất, thuật ngữ và các phép toán cơ bản trên cây là bước đệm quan trọng để tiếp cận các thuật toán phức tạp hơn, đặc biệt là trong các bài toán tìm kiếm, sắp xếp và tối ưu hóa.

1.1. Định nghĩa và các khái niệm cơ bản về cấu trúc cây

Một cấu trúc dữ liệu cây được định nghĩa một cách đệ quy. Bước cơ sở xác định rằng một nút đơn lẻ r là một cây, và r được gọi là gốc của cây đó. Bước quy nạp cho phép xây dựng một cây mới bằng cách đặt một nút r làm cha của các gốc r1, r2, ..., rk của các cây có sẵn T1, T2, ..., Tk. Trong cây mới này, r là gốc, và T1, T2, ..., Tk trở thành các cây con (subtree). Ngoài ra, các thuật ngữ quan trọng khác bao gồm: lá (leaf) là nút không có con; nút trong (internal node) là nút không phải lá; tổ tiên (ancestors) và hậu duệ (descendants) mô tả mối quan hệ phân cấp. Chiều cao (height) của một nút là đường đi dài nhất từ nút đó đến một lá, trong khi độ sâu (depth) là độ dài đường đi từ gốc đến nút đó. Bậc (degree) của một nút là số lượng con của nó. Những khái niệm này là nền tảng để phân tích và triển khai các thuật toán liên quan đến cây.

1.2. Các ứng dụng thực tế của cây trong khoa học máy tính

Cấu trúc cây không chỉ là một khái niệm lý thuyết mà còn có vô số ứng dụng thực tiễn. Cây thư mục trong hệ điều hành là một ví dụ điển hình, nơi mỗi thư mục là một nút và có thể chứa các tệp (lá) hoặc các thư mục con. Cây gia phả thể hiện mối quan hệ huyết thống một cách trực quan. Trong lĩnh vực thể thao, cây lịch thi đấu được dùng để theo dõi các trận đấu loại trực tiếp. Một ứng dụng quan trọng khác là cây biểu thức (expression tree), dùng để biểu diễn các biểu thức số học, nơi các toán hạng là lá và các phép toán là nút trong. Ngoài ra, cây quyết định (decision tree) là một công cụ mạnh mẽ trong học máy và trí tuệ nhân tạo để phân loại dữ liệu. Việc hiểu các ứng dụng này giúp nhận thức rõ hơn về sức mạnh và tính linh hoạt của cấu trúc dữ liệu cây trong việc giải quyết các bài toán phức tạp.

II. Thách thức duyệt cây Hướng dẫn 3 phương pháp duyệt hiệu quả

Duyệt cây (tree traversal) là quá trình truy cập (thăm) tất cả các nút trong cây một cách có hệ thống, mỗi nút đúng một lần. Do cấu trúc phi tuyến của cây, việc duyệt không đơn giản như duyệt một mảng từ đầu đến cuối. Các thuật toán duyệt cây cung cấp một trình tự xác định để xử lý thông tin tại mỗi nút, là cơ sở cho nhiều thao tác phức tạp khác như tìm kiếm, sao chép, hoặc xóa cây. Có ba phương pháp duyệt đệ quy phổ biến và quan trọng nhất, được định nghĩa dựa trên thứ tự thăm nút gốc so với các cây con của nó: Thứ tự trước (Preorder), Thứ tự sau (Postorder), và Thứ tự giữa (Inorder). Mỗi phương pháp duyệt này tạo ra một chuỗi các nút khác nhau và phục vụ cho những mục đích riêng biệt. Ví dụ, duyệt theo thứ tự trước thường được dùng để tạo bản sao của cây, trong khi duyệt theo thứ tự sau hữu ích trong việc giải phóng bộ nhớ của cây. Việc lựa chọn phương pháp duyệt phù hợp phụ thuộc hoàn toàn vào yêu cầu của bài toán cụ thể, và nắm vững cả ba phương pháp là kỹ năng thiết yếu khi làm việc với cấu trúc dữ liệu và thuật toán liên quan đến cây.

2.1. Phân tích thuật toán duyệt cây theo thứ tự trước Preorder

Duyệt theo thứ tự trước (Preorder Traversal) tuân theo quy tắc "Gốc - Trái - Phải". Thuật toán được định nghĩa đệ quy như sau: đầu tiên, thăm nút gốc; tiếp theo, duyệt cây con trái nhất theo thứ tự trước; sau đó, lần lượt duyệt các cây con còn lại từ trái sang phải theo thứ tự trước. Theo tài liệu, thuật toán PREORDER(nodeT r) được mô tả: "(1) Đưa ra r; (2) for (mỗi con c của r) do PREORDER(c);". Cách duyệt này đảm bảo rằng một nút cha luôn được xử lý trước các nút con của nó. Ứng dụng tiêu biểu của Preorder là khi cần sao chép một cây, vì nó tạo ra một bản sao có cấu trúc giống hệt cây gốc. Trong cây biểu thức, duyệt theo thứ tự trước sẽ cho ra biểu thức ở dạng tiền tố (ký pháp Ba Lan).

2.2. Khám phá thuật toán duyệt cây theo thứ tự sau Postorder

Trái ngược với Preorder, duyệt theo thứ tự sau (Postorder Traversal) tuân theo quy tắc "Trái - Phải - Gốc". Thuật toán này duyệt tất cả các cây con từ trái sang phải theo thứ tự sau trước, và cuối cùng mới thăm nút gốc. Tài liệu mô tả thuật toán POSTORDER(nodeT r) bằng cách "đảo ngược hai thao tác (1) và (2) trong PREORDER". Cụ thể là: "for (mỗi con c của r) do POSTORDER(c); (2) Đưa ra r;". Vì nút gốc luôn được thăm sau cùng, phương pháp này rất hữu ích trong các tác vụ cần xử lý các nút con trước khi xử lý nút cha. Một ứng dụng điển hình là việc xóa một cây và giải phóng bộ nhớ, vì không thể xóa một nút cha trước khi các con của nó đã được xóa. Đối với cây biểu thức, duyệt theo thứ tự sau sẽ cho ra biểu thức ở dạng hậu tố (ký pháp Ba Lan ngược), rất thuận tiện cho việc tính toán bằng stack.

2.3. Tìm hiểu thuật toán duyệt theo thứ tự giữa Inorder

Duyệt theo thứ tự giữa (Inorder Traversal) chủ yếu được áp dụng cho cây nhị phân và tuân theo quy tắc "Trái - Gốc - Phải". Định nghĩa đệ quy của nó là: đầu tiên, duyệt cây con trái theo thứ tự giữa; tiếp theo, thăm nút gốc; và cuối cùng, duyệt cây con phải theo thứ tự giữa. Đối với cây tổng quát có nhiều hơn hai con, khái niệm này được mở rộng: duyệt cây con trái nhất, sau đó thăm gốc, và cuối cùng duyệt các cây con còn lại. Một trong những ứng dụng quan trọng nhất của Inorder traversal là trên cây tìm kiếm nhị phân. Khi duyệt một cây tìm kiếm nhị phân theo thứ tự giữa, các giá trị tại các nút sẽ được liệt kê theo thứ tự tăng dần. Điều này làm cho Inorder trở thành một phương pháp sắp xếp tự nhiên khi dữ liệu được tổ chức trong cấu trúc này.

III. Cây nhị phân Cấu trúc dữ liệu và các tính chất cơ bản nhất

Cây nhị phân (Binary Tree) là một dạng cây đặc biệt và được sử dụng rộng rãi nhất trong cấu trúc dữ liệu và thuật toán. Theo định nghĩa, cây nhị phân là cây mà mỗi nút có nhiều nhất hai con. Hai con này được phân biệt rõ ràng là con trái (left child) và con phải (right child). Điều này tạo ra một sự khác biệt quan trọng so với cây tổng quát, ngay cả khi một nút chỉ có một con, việc nó là con trái hay con phải cũng mang ý nghĩa cấu trúc. Cây nhị phân là nền tảng cho nhiều cấu trúc dữ liệu hiệu quả khác như cây tìm kiếm nhị phân, cây heap, và cây Huffman. Việc nghiên cứu các tính chất của nó, chẳng hạn như mối quan hệ giữa chiều cao và số lượng nút, là rất quan trọng. Ví dụ, một cây nhị phân có chiều cao k có không quá 2^k - 1 nút. Hiểu rõ các biến thể của cây nhị phân như cây nhị phân đầy đủ, cây nhị phân hoàn chỉnh, và cây nhị phân cân bằng giúp lựa chọn cấu trúc phù hợp để tối ưu hóa hiệu suất của các thuật toán.

3.1. Tính chất và đặc điểm của một cây nhị phân tiêu chuẩn

Một cây nhị phân sở hữu nhiều tính chất toán học quan trọng. Bổ đề 1 trong tài liệu chỉ ra rằng: (i) số nút lớn nhất ở mức i là 2^(i-1); (ii) một cây nhị phân với chiều cao k có tối đa 2^k - 1 nút; và (iii) một cây nhị phân n nút có chiều cao tối thiểu là ceil(log2(n+1)). Những tính chất này cung cấp giới hạn trên và dưới cho hiệu suất của các thuật toán hoạt động trên cây. Chẳng hạn, trong một cây nhị phân cân bằng, thời gian tìm kiếm một phần tử là O(log n) vì chiều cao của nó được giữ ở mức tối thiểu. Việc phân biệt con trái và con phải cũng là đặc điểm cốt lõi, làm cho hai cây có cùng các nút nhưng thứ tự con khác nhau được coi là hai cây nhị phân khác nhau.

3.2. Phân biệt cây nhị phân đầy đủ hoàn chỉnh và cân bằng

Có ba loại cây nhị phân đặc biệt thường được đề cập. Cây nhị phân đầy đủ (Full Binary Tree) là cây mà mọi nút trong đều có đúng hai con và tất cả các lá đều có cùng độ sâu. Cây nhị phân hoàn chỉnh (Complete Binary Tree) là cây nhị phân mà tất cả các mức, trừ mức cuối cùng, đều được lấp đầy, và các nút ở mức cuối cùng được lấp đầy từ trái sang phải. Cấu trúc này rất lý tưởng cho việc biểu diễn bằng mảng. Cuối cùng, cây nhị phân cân bằng (Balanced Binary Tree) là cây mà tại mọi nút, chênh lệch chiều cao giữa cây con trái và cây con phải không quá 1. Cây đầy đủ là cây hoàn chỉnh, và cây hoàn chỉnh cũng là cây cân bằng, nhưng điều ngược lại không phải lúc nào cũng đúng. Việc duy trì tính cân bằng là chìa khóa để đảm bảo hiệu suất O(log n) cho các thao tác tìm kiếm, chèn, xóa.

IV. Cách biểu diễn cây Từ mảng đến con trỏ trong lập trình

Để triển khai cấu trúc dữ liệu cây trong một chương trình máy tính, cần có một phương pháp biểu diễn hiệu quả. Việc lựa chọn cách biểu diễn ảnh hưởng trực tiếp đến hiệu suất của các thuật toán thao tác trên cây. Có hai phương pháp chính: sử dụng mảng và sử dụng con trỏ. Biểu diễn cây dùng mảng đặc biệt hiệu quả đối với cây nhị phân hoàn chỉnh. Trong phương pháp này, mối quan hệ cha-con có thể được suy ra trực tiếp từ chỉ số của mảng. Ví dụ, với nút tại chỉ số i, con trái của nó sẽ ở 2*i và con phải ở 2*i+1. Tuy nhiên, phương pháp này rất lãng phí bộ nhớ đối với các cây không hoàn chỉnh. Ngược lại, biểu diễn cây dùng con trỏ linh hoạt hơn rất nhiều. Mỗi nút được biểu diễn bằng một cấu trúc (struct) chứa dữ liệu và các con trỏ đến các nút con của nó. Đối với cây tổng quát, có thể dùng danh sách các con hoặc biểu diễn "con trái nhất, em kế cận phải". Đối với cây nhị phân, mỗi nút chỉ cần hai con trỏ: một cho con trái và một cho con phải, đây là cách tiếp cận phổ biến và trực quan nhất.

4.1. Phương pháp biểu diễn cây bằng mảng và các ưu nhược điểm

Biểu diễn cây nhị phân hoàn chỉnh bằng mảng là một kỹ thuật rất hiệu quả. Các nút được đánh số từ trên xuống dưới và từ trái qua phải, bắt đầu từ 1. Nút i sẽ được lưu tại phần tử A[i] của mảng. Từ đó, ta có thể tìm nút cha của A[i] tại A[floor(i/2)], con trái tại A[2*i], và con phải tại A[2*i+1]. Ưu điểm của phương pháp này là tiết kiệm không gian bộ nhớ do không cần lưu các con trỏ và cho phép truy cập cha-con nhanh chóng. Tuy nhiên, nhược điểm lớn là sự lãng phí bộ nhớ khi cây thưa hoặc không cân bằng. Nếu một cây có chiều cao lớn nhưng ít nút, mảng biểu diễn sẽ có rất nhiều ô trống, làm cho phương pháp này không thực tế trong nhiều trường hợp.

4.2. Kỹ thuật biểu diễn cây bằng cấu trúc con trỏ linh hoạt

Phương pháp biểu diễn cây dùng con trỏ là cách tiếp cận phổ biến và linh hoạt nhất. Mỗi nút được định nghĩa là một cấu trúc dữ liệu, ví dụ trong ngôn ngữ C: struct Tnode { DataType Item; struct Tnode *left; struct Tnode *right; };. Cấu trúc này chứa dữ liệu (Item) và hai con trỏ, một đến con trái (left) và một đến con phải (right). Nếu một nút không có con trái hoặc con phải, con trỏ tương ứng sẽ được gán giá trị NULL. Ưu điểm của phương pháp này là chỉ cấp phát bộ nhớ cho các nút thực sự tồn tại, do đó rất hiệu quả về không gian cho mọi loại cây. Nó cũng cho phép các thao tác chèn và xóa nút một cách linh hoạt mà không cần phải di chuyển một lượng lớn dữ liệu như trong biểu diễn mảng.

V. Top ứng dụng của cấu trúc dữ liệu cây trong các bài toán thực tế

Cấu trúc dữ liệu cây và các thuật toán liên quan không chỉ là những khái niệm trừu tượng mà còn là công cụ giải quyết vô số bài toán trong thế giới thực. Sức mạnh của cây nằm ở khả năng mô hình hóa các mối quan hệ phân cấp và cho phép các thao tác tìm kiếm, truy vấn hiệu quả. Một trong những ứng dụng phổ biến nhất là cây biểu thức nhị phân, được sử dụng bởi các trình biên dịch để phân tích và tính toán giá trị của các biểu thức toán học. Một lĩnh vực khác là học máy, nơi cây quyết định được dùng làm mô hình dự đoán để phân loại dữ liệu dựa trên một chuỗi các câu hỏi. Ngoài ra, trong lĩnh vực nén dữ liệu, Mã Huffman (Huffman Code) sử dụng cây nhị phân để xây dựng một bộ mã có độ dài thay đổi, giúp giảm đáng kể kích thước của tệp tin mà không làm mất thông tin. Những ví dụ này chỉ là một phần nhỏ, cho thấy tầm quan trọng và tính ứng dụng rộng rãi của cây trong công nghệ hiện đại.

5.1. Cây biểu thức nhị phân và việc tính toán biểu thức

Cây biểu thức nhị phân (Binary Expression Tree) là một ứng dụng trực tiếp của cây nhị phân để biểu diễn các biểu thức số học. Trong cây này, mỗi nút lá chứa một toán hạng (số hoặc biến), và mỗi nút trong chứa một phép toán hai ngôi. Cây con trái và phải của một nút phép toán biểu diễn các biểu thức con. Ưu điểm của cấu trúc này là thứ tự ưu tiên của các phép toán được xác định rõ ràng bởi cấu trúc của cây mà không cần dùng đến dấu ngoặc. Bằng cách áp dụng các phương pháp duyệt cây, ta có thể dễ dàng thu được các dạng biểu diễn khác nhau: duyệt theo thứ tự giữa (Inorder) cho ra dạng trung tố (dạng viết thông thường), duyệt theo thứ tự trước (Preorder) cho ra dạng tiền tố, và duyệt theo thứ tự sau (Postorder) cho ra dạng hậu tố. Dạng hậu tố đặc biệt hữu ích cho việc tính toán hiệu quả bằng cấu trúc dữ liệu stack.

5.2. Mã Huffman Ứng dụng cây nhị phân trong nén dữ liệu

Mã Huffman là một thuật toán nén dữ liệu không mất mát, dựa trên tần suất xuất hiện của các ký tự. Ý tưởng cốt lõi là sử dụng các mã nhị phân có độ dài thay đổi: các ký tự xuất hiện thường xuyên được gán mã ngắn hơn, còn các ký tự ít xuất hiện được gán mã dài hơn. Để xây dựng bộ mã này, thuật toán Huffman sử dụng một cây nhị phân. Ban đầu, mỗi ký tự được xem là một nút lá với trọng số là tần suất của nó. Thuật toán lặp đi lặp lại việc kết hợp hai nút có tần suất thấp nhất để tạo thành một nút cha mới, có tần suất bằng tổng tần suất của hai con. Quá trình này tiếp tục cho đến khi chỉ còn lại một cây duy nhất. Mã của mỗi ký tự được xác định bằng đường đi từ gốc đến lá tương ứng (ví dụ: rẽ trái là 0, rẽ phải là 1). Kết quả là một bộ mã tiền tố (prefix code), đảm bảo việc giải mã là duy nhất và hiệu quả.

VI. Kết luận Tầm quan trọng của cây trong khoa học máy tính

Qua các phân tích về định nghĩa, thuộc tính, các phương pháp duyệt và ứng dụng, có thể khẳng định rằng cấu trúc dữ liệu cây là một trong những khái niệm nền tảng và mạnh mẽ nhất trong khoa học máy tính. Khả năng biểu diễn dữ liệu phân cấp một cách tự nhiên giúp nó trở thành lựa chọn tối ưu cho nhiều bài toán, từ quản lý hệ thống tệp đến phân tích cú pháp trong trình biên dịch và các mô hình học máy. Đặc biệt, cây nhị phân và các biến thể của nó như cây tìm kiếm nhị phân hay cây heap đã tạo ra những thuật toán có hiệu suất vượt trội, cho phép xử lý các tập dữ liệu lớn với thời gian tiệm cận logarit. Việc nắm vững các khái niệm từ cơ bản như nút, gốc, lá đến các kỹ thuật phức tạp như duyệt cây hay cân bằng cây là kỹ năng không thể thiếu đối với bất kỳ lập trình viên hay kỹ sư phần mềm nào. Cấu trúc cây không chỉ là một công cụ, mà còn là một lối tư duy để mô hình hóa và giải quyết vấn đề một cách hiệu quả và có hệ thống.

6.1. Tóm tắt vai trò của cấu trúc dữ liệu cây và thuật toán

Cấu trúc dữ liệu cây đóng vai trò trung tâm trong việc tổ chức dữ liệu theo một cấu trúc phân cấp, phản ánh nhiều hệ thống trong thực tế. Nó cung cấp một giải pháp hiệu quả hơn so với các cấu trúc tuyến tính khi giải quyết các bài toán liên quan đến tìm kiếm và sắp xếp phân cấp. Các thuật toán như duyệt cây (Preorder, Inorder, Postorder) cung cấp các phương pháp có hệ thống để xử lý mọi nút trong cây, phục vụ cho vô số ứng dụng. Các cấu trúc chuyên biệt như cây nhị phân và các biến thể của nó đã chứng tỏ hiệu quả vượt trội, đặc biệt là cây tìm kiếm nhị phân cân bằng, giúp giảm độ phức tạp thời gian của các thao tác cơ bản xuống O(log n). Tóm lại, cây là một công cụ không thể thay thế, là cầu nối giữa lý thuyết thuật toán và các ứng dụng thực tiễn.

6.2. Hướng phát triển và các cấu trúc cây nâng cao trong tương lai

Lĩnh vực cấu trúc dữ liệu và thuật toán luôn không ngừng phát triển. Dựa trên nền tảng của cây nhị phân, nhiều cấu trúc cây nâng cao đã được ra đời để giải quyết các bài toán chuyên biệt hơn. Ví dụ, B-Tree và các biến thể của nó (B+ Tree, B* Tree) là cấu trúc nền tảng của hầu hết các hệ quản trị cơ sở dữ liệu và hệ thống tệp hiện đại, được tối ưu cho việc truy xuất dữ liệu trên bộ nhớ ngoài. Cây Đỏ-Đen (Red-Black Tree) và cây AVL là các loại cây tìm kiếm nhị phân tự cân bằng, đảm bảo hiệu suất ổn định trong trường hợp xấu nhất. Trong đồ họa máy tính và tìm kiếm không gian, các cấu trúc như K-D Tree hay Quadtree được sử dụng để phân hoạch không gian một cách hiệu quả. Việc nghiên cứu và ứng dụng các cấu trúc cây nâng cao này sẽ tiếp tục là một hướng đi quan trọng, mở ra những giải pháp tối ưu hơn cho các thách thức công nghệ trong tương lai.

Nội dung chính

TÀI LIỆU HỌC THUẬT: CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT – CHUYÊN ĐỀ CẤU TRÚC CÂY VÀ THUẬT TOÁN SẮP XẾP

---

Tổng quan về giáo trình (250-300 từ)

Tài liệu thuộc khối kiến thức cơ sở ngành bắt buộc trong chương trình đào tạo Cử nhân và Kỹ sư các ngành Công nghệ thông tin, Khoa học máy tính và Kỹ thuật phần mềm ở bậc đại học. Nội dung văn bản tập trung vào hai chủ đề nền tảng của môn học Cấu trúc dữ liệu và Giải thuật: Cấu trúc Cây (Chương 4) và Các thuật toán Sắp xếp (Chương 5).

Mục tiêu học tập (learning outcomes) của học phần bao gồm:

• Định nghĩa hình thức cấu trúc cây và cây nhị phân bằng phương pháp đệ quy;
• Nắm vững các phương pháp biểu diễn dữ liệu trừu tượng (ADT) của cây thông qua cấu trúc mảng và danh sách liên kết;
• Hiện thực hóa các thuật toán duyệt cây (Preorder, Inorder, Postorder) và các phép toán cơ bản trên ngôn ngữ lập trình C;
• Phân tích tính chất toán học của các dạng cây nhị phân đặc thù (đầy đủ, hoàn chỉnh, cân đối);
• Vận dụng cấu trúc cây vào việc giải quyết các bài toán ứng dụng: cây biểu thức, mô hình cây quyết định để đánh giá cận dưới độ phức tạp tính toán, và thuật toán nén dữ liệu tối ưu Huffman;
• Hiểu rõ nguyên lý phân loại, đặc trưng kỹ thuật và cận dưới lý thuyết của các thuật toán sắp xếp dữ liệu.

Cấu trúc giáo trình tiếp cận theo mô hình phân tầng chặt chẽ: từ định nghĩa toán học và hình học trực quan, xây dựng kiểu dữ liệu trừu tượng (ADT), hiện thực hóa bằng mã nguồn lập trình C, đến phân tích đánh giá độ phức tạp thuật toán và giải quyết các bài toán ứng dụng thực tế.

Điểm đặc sắc của giáo trình là sự gắn kết trực tiếp giữa các tiên đề toán học với các mô hình thực tiễn (như cấu trúc quản lý hành chính, cây thư mục hệ thống tệp, cây phả hệ dòng họ toán học Bernoulli, cây biểu thức số học) và hệ thống mã nguồn mẫu hoàn chỉnh có thể biên dịch và thực thi trực tiếp.

---

Nội dung kiến thức cốt lõi (500-600 từ)

Các chương/chủ đề chính

Nội dung cốt lõi của phần tài liệu bao gồm hai chương trọng tâm:

1. Chương 4: Cây (Tree)

• Định nghĩa và thuật ngữ: Cây được định nghĩa đệ quy gồm bước cơ sở (nút gốc $r$) và bước quy nạp (gốc $r$ làm cha của các cây con $T_1, T_2, \dots, T_k$). Hệ thống thuật ngữ kỹ thuật gồm: nút (node), gốc (root), lá (leaf), con (child), cha (parent), tổ tiên (ancestors), hậu duệ (descendants), anh em (sibling), nút trong (internal node), chiều cao (height), độ sâu/mức (depth/level), bậc (degree), đường đi (path).
• Cây có thứ tự và các phương pháp duyệt: Quy tắc xác định thứ tự trái/phải giữa các nút anh em. Ba thuật toán duyệt đệ quy cơ bản: Duyệt trước (Preorder Traversal – NLR), Duyệt giữa (Inorder Traversal – LNR), Duyệt sau (Postorder Traversal – LRN). Công thức xác định quan hệ tổ tiên – hậu duệ qua thứ tự duyệt sau: $postorder(y) - desc(y) < postorder(x) \le postorder(y)$.
• Cây có nhãn và Cây biểu thức: Biểu diễn biểu thức số học (toán tử tại nút trong, toán hạng tại nút lá).
• Kiểu dữ liệu trừu tượng (ADT) Cây và các cấu trúc biểu diễn: Các hàm nguyên mẫu (parent, leftmost_child, right_sibling, label, create_i, root, makenull). Ba phương pháp biểu diễn: Mảng con trỏ cha $A[i]$, Danh sách các con (Lists of Children), Dùng con trái và em kề cận phải (Leftmost-Child, Right-Sibling).
• Cây nhị phân (Binary Tree): Định nghĩa và các dạng đặc thù (Cây nhị phân đầy đủ - Full binary tree, Cây nhị phân hoàn chỉnh - Complete binary tree, Cây nhị phân cân đối - Balanced binary tree). Biểu diễn bằng mảng chỉ mục và con trỏ kép (left, right). Mã nguồn cài đặt C cho các hàm: tạo nút (makeTreeNode), chèn ngẫu nhiên (RandomInsert), giải phóng bộ nhớ (freeTree), đếm số nút (countNodes), tính độ sâu (depth), và in thứ tự duyệt.
• Các ứng dụng tiêu biểu: Cây nhị phân biểu thức (chuyển đổi tiền tố - Prefix, trung tố - Infix, hậu tố - Postfix); Cây quyết định (Decision Trees) chứng minh độ phức tạp bài toán tra từ điển và cận dưới bài toán sắp xếp so sánh; Thuật toán mã hóa và giải mã Huffman (Huffman Code) dựa trên tần suất ký tự và hàng đợi ưu tiên (Priority Queue).

2. Chương 5: Các thuật toán sắp xếp (Sorting Algorithms)

• Khái niệm cơ sở: Định nghĩa sắp xếp trên dãy $A = (a_1, a_2, \dots, a_n)$, cấu trúc khóa sắp xếp (Sort key) và bảng khóa (khóa, con trỏ).
• Phân loại và đặc trưng kỹ thuật: Sắp xếp trong (Internal sort), Sắp xếp ngoài (External sort); Thuật toán tại chỗ (In-place, không gian nhớ phụ $O(1)$); Thuật toán ổn định (Stable). Các phép toán cơ bản: swap và Compare.
• Phân loại 15 thuật toán sắp xếp dựa trên so sánh: Đơn giản ($O(n^2)$: Bubble sort, Selection sort, Insertion sort, Cocktail sort, Gnome sort), Hiệu quả ($O(n \log n)$: Merge sort, Quick sort, Heap sort, Binary tree sort, Comb sort, Library sort, Smooth sort, Intro sort, Patience sorting).

Kiến thức nền tảng được xây dựng

• Lý thuyết toán học: Các bổ đề về cận số lượng nút cực đại trên mức $i$ ($2^{i-1}$), số lượng nút cực đại của cây chiều cao $k$ ($2^k - 1$), và chiều cao tối thiểu của cây $n$ nút ($\lceil\log_2(n+1)\rceil$).
• Nguyên lý thiết kế: Tách biệt giữa giao diện Kiểu dữ liệu trừu tượng (ADT) và cấu trúc lưu trữ dữ liệu cụ thể; nguyên lý giải thuật đệ quy trên cấu trúc phân cấp.
• Mô hình tính toán: Sử dụng mô hình cây quyết định để đánh giá cận dưới lý thuyết cho mọi thuật toán sắp xếp dựa trên phép so sánh là $\Omega(n \log n)$.

Kỹ năng phát triển

• Kỹ năng kỹ thuật: Cài đặt cấu trúc dữ liệu động trên ngôn ngữ C bằng con trỏ và cấp phát bộ nhớ động (malloc, free); viết hàm đệ quy thao tác trên cây.
• Kỹ năng phân tích: Đánh giá độ phức tạp thời gian và không gian bộ nhớ của giải thuật qua ký hiệu tiệm cận $O$ và $\Omega$; chứng minh quy nạp toán học các tính chất của cây.
• Kỹ năng ứng dụng: Xây dựng thuật toán nén/giải mã tối ưu dữ liệu (Huffman); chuyển đổi và tính toán giá trị biểu thức số học.

---

Phương pháp giảng dạy và học tập (300-350 từ)

Giáo trình áp dụng phương pháp sư phạm diễn dịch kết hợp quy nạp, dẫn dắt người học từ trực quan mô hình hóa thực tế (biểu đồ lịch thi đấu World Cup, cây phân cấp tổ chức doanh nghiệp, cây thư mục tệp tin máy tính) đến hệ thống hóa các định nghĩa toán học đệ quy chặt chẽ.

Phương pháp giảng dạy và học tập bao gồm các cấu phần:

• Minh họa thuật toán bằng mã nguồn thực thi: Giáo trình cung cấp mã nguồn C hoàn chỉnh cho chương trình kiểm thử duyệt cây nhị phân (The program for testing binary tree traversal), bao gồm các hàm thao tác con trỏ tường minh như makeTreeNode, RandomInsert, freeTree, printPreorder, printInorder, printPostorder, countNodes, depth.
• Hệ thống bài tập chuyên đề: Cuối Chương 4 cung cấp hệ thống 24 bài tập thực hành bao quát các mức độ:
  • Mức độ phân tích và tính toán: Xác định thứ tự duyệt cây (NLR, LNR, LRN); vẽ cây nhị phân từ dãy khóa duyệt sau; chuyển đổi biểu thức trung tố sang tiền tố/hậu tố và tính giá trị biểu thức hậu tố với các tham số cụ thể ($a=5, b=10, c=7, d=20, e=5, f=3, g=5$).
  • Mức độ lập trình và cài đặt trên C: Viết các hàm đệ quy tính toán trên cấu trúc struct Tnode hoặc struct TreeNode: đếm số lá có giá trị chẵn (EvenLeaf), đếm nút có khóa lớn hơn $k$ (countNodes), kiểm tra tính đẳng cấu giữa hai cây (isometric), lấy phản xạ gương cây nhị phân (mirror), tính tổng số lẻ (OddSum), tìm giá trị chẵn lớn nhất trong cây tìm kiếm nhị phân (EvenMax), kiểm tra cây nhị phân cân bằng (IsBST), tính đường kính cây (BT_Diam), kiểm tra khóa nút (IsLeft).
  • Mức độ giải thuật nâng cao: Xây dựng cây mã Huffman từ bảng phân bố tần suất ký tự, lập bảng mã và giải mã chuỗi nhị phân (như giải mã chuỗi 001000111101001101100).
• Phương pháp tự học: Người học được hướng dẫn phương pháp trực quan để nhớ quy tắc duyệt cây bằng cách "đi vòng quanh bên ngoài cây, bắt đầu từ gốc, ngược chiều kim đồng hồ và sát theo cây nhất" để xác định chính xác thời điểm in dữ liệu của từng nút.

---

Điểm nổi bật và cập nhật (250-300 từ)

• Tính chặt chẽ trong chứng minh toán học: Các tính chất của cây nhị phân đều đi kèm chứng minh quy nạp toán học chi tiết (Bổ đề 1, Bổ đề 2, Bổ đề 3), cung cấp cơ sở lý thuyết cho việc tính toán chiều cao và số lượng nút.
• Mô hình hóa lý thuyết thông tin: Tích hợp công trình thuật toán nén dữ liệu tối ưu của David A. Huffman (1925–1999). Giáo trình đối sánh định lượng chi tiết giữa phương pháp mã hóa độ dài cố định (5 bit/ký tự cho bảng chữ cái tiếng Anh) với mã Huffman phi tiền tố (Prefix-free code), minh chứng qua bảng số liệu thực tế giảm tổng độ dài từ 3382 bit xuống 3036 bit trên tập dữ liệu mẫu 838 ký tự.
• Chứng minh cận dưới của bài toán sắp xếp: Sử dụng mô hình cây quyết định nhị phân có $n!$ lá tương ứng với $n!$ hoán vị để chứng minh bằng toán học rằng chiều cao cây đạt mức tối thiểu $\Omega(\log n!) = \Omega(n \log n)$, khẳng định không một thuật toán sắp xếp dựa trên phép so sánh nào có thể vượt qua cận dưới này.
• Dữ liệu thực tế và tính trực quan: Trích xuất các sơ đồ thực tế như cây gia phả dòng họ toán học Bernoulli (Nikolaus, Johan I, Jacob I, Daniel...), cấu trúc thư mục máy tính thực tế (UMBC CMSC 441, DM_Far_Vd...), và trích dẫn kinh điển của Donald Knuth: "40% thời gian hoạt động của các máy tính là dành cho Sắp xếp!".
• Bảng phân loại đối sánh 15 thuật toán sắp xếp: Tổng hợp toàn diện các chỉ số kỹ thuật gồm độ phức tạp trung bình, trường hợp xấu nhất, bộ nhớ phụ, tính ổn định và phương pháp thực hiện (Hoán đổi, Chọn, Chèn, Trộn, Phân chia).

---

Đối tượng sử dụng giáo trình (200-250 từ)

• Sinh viên đại học: Dành cho sinh viên năm thứ hai thuộc các ngành Công nghệ thông tin, Khoa học máy tính, Kỹ thuật phần mềm, Hệ thống thông tin, An toàn thông tin đang theo học học phần Cấu trúc dữ liệu và Giải thuật.
• Kiến thức tiên quyết (Prerequisites):
  • Kỹ năng lập trình ngôn ngữ C/C++ cơ bản và nâng cao: thành thạo cấu trúc con trỏ, mảng, bản ghi (struct), cấp phát và giải phóng bộ nhớ động (malloc, free), kỹ thuật viết hàm đệ quy.
  • Toán rời rạc: nắm vững lý thuyết tập hợp, quan hệ, logic mệnh đề, lý thuyết đồ thị cơ bản và phương pháp chứng minh quy nạp toán học.
• Giảng viên: Tài liệu cung cấp khung bài giảng lý thuyết chuẩn mực, hệ thống mã nguồn mẫu C chuẩn để tổ chức các buổi thực hành trên máy (lab programming), và ngân hàng 24 bài tập chuyên sâu phục vụ thiết kế đề kiểm tra, đề thi kết thúc học phần.
• Tự học và tham khảo học thuật: Tài liệu phù hợp cho sinh viên tự học, ôn luyện thi Olympic Tin học sinh viên, hoặc người lập trình củng cố nền tảng cấu trúc dữ liệu phục vụ các kỳ đánh giá kỹ thuật chuyên môn.

---

Câu hỏi thường gặp (250-300 từ)

1. Giáo trình này phù hợp với đối tượng người học nào?

Giáo trình được thiết kế chuẩn hóa cho sinh viên đại học khối ngành Công nghệ thông tin và Khoa học máy tính học học phần Cấu trúc dữ liệu và Giải thuật, cũng như người học cần nghiên cứu sâu về cấu trúc dữ liệu phân cấp và thuật toán tối ưu.

2. Cần chuẩn bị những kiến thức nền tảng nào trước khi học nội dung này?

Người học cần nắm vững kỹ thuật lập trình C (đặc biệt là con trỏ, cấu trúc struct, hàm đệ quy, cấp phát bộ nhớ động malloc/free) và kiến thức Toán rời rạc (chứng minh quy nạp, ký hiệu tiệm cận $O, \Omega$).

3. Điểm khác biệt của tài liệu này so với các giáo trình lập trình thông thường là gì?

Tài liệu không thuần túy dạy cú pháp ngôn ngữ lập trình mà tập trung vào mô hình toán học, kiểu dữ liệu trừu tượng (ADT), chứng minh tính chất bằng quy nạp, đánh giá cận dưới độ phức tạp tính toán thông qua cây quyết định và tối ưu hóa giải thuật (mã Huffman).

4. Phương pháp tự học nội dung cấu trúc Cây như thế nào để đạt hiệu quả cao?

Người học nên kết hợp vẽ trực quan cây dữ liệu, lần vết (trace) thứ tự duyệt theo quy tắc đường biên ngược chiều kim đồng hồ, tự cài đặt lại các hàm C mẫu trong tài liệu và hoàn thành hệ thống 24 bài tập lập trình đệ quy ở cuối chương.

5. Có những tài liệu bổ trợ và mã nguồn mẫu nào kèm theo giáo trình?

Giáo trình cung cấp sẵn chương trình C hoàn chỉnh để kiểm thử các phép toán trên cây nhị phân, bảng tổng hợp phân loại 15 thuật toán sắp xếp, và bảng thống kê tần suất ký tự mẫu phục vụ bài toán mã hóa Huffman.

---

Kết luận (150 từ)

Giáo trình cung cấp hệ thống tri thức chuẩn mực về cấu trúc dữ liệu phân cấp (Cây) và các phương pháp xử lý dữ liệu nền tảng (Sắp xếp). Giá trị cốt lõi của tài liệu nằm ở sự kết hợp giữa tính chặt chẽ của lý thuyết toán học (định nghĩa đệ quy, các bổ đề giới hạn, chứng minh cận dưới $\Omega(n \log n)$) với khả năng ứng dụng thực tế thông qua mã nguồn C hoàn chỉnh và các bài toán nén dữ liệu Huffman, cây quyết định, cây biểu thức.

Lộ trình học tập đề xuất:

1. Nắm vững định nghĩa đệ quy và các phép toán trên ADT Cây;
2. Thành thạo các giải thuật duyệt cây và cài đặt cây nhị phân trên ngôn ngữ C;
3. Khai thác các ứng dụng nâng cao (Cây biểu thức, Cây quyết định, Mã Huffman);
4. Nghiên cứu nguyên lý phân loại và đặc trưng kỹ thuật của các thuật toán sắp xếp;
5. Giải quyết toàn bộ 24 bài tập lập trình và phân tích ở cuối chương.

Trích đoạn nội dung tài liệu

ĐỊNH NGHĨA VÀ CÁC KHÁI NIỆM 4. Định nghĩa cây Cây bao gồm các nút, có một nút đặc biệt được gọi là gốc (root) và các cạnh nối các nút. Cây được định nghĩa đệ quy như sau: Định nghĩa cây Bước cơ sở: Một nút r là cây và r được gọi là gốc của cây này. Bước quy nạp: Giả sử 7¡, 7;,., 7; là các cây với gốc là rụ, ra.

Ta có thể xây dựng cây mới bang cach dat r lam cha (parent) của các nút r\, 7a,. Trong cây nay r là gôc và 7\, 7›,., 7¿ là các cây con của gôc z., r¿ được gọi là con của nút z. Chú ý: Nhiều khi để phù hợp, ta cần định nghĩa cây rỗng (null tree) là cây không có nút nào cả. Cầu trúc đệ quy của cây Cây trong thực tế ứng dụng ~ Biểu đồ lịch thí đầu.

— Cây gia phả. — Biểu đồ phân cấp quản lý hành chính. — Cây thư mục. — Cầu trúc của một quyển sách.

143 ~ Cây biểu thức. ~ Cay phân hoạch tập hợp. Cây lịch thi đấu Trong đời thường, cây rất hay được sử dụng để diễn tả lịch thi đấu của các giải thé thao theo thể thức đầu loại trực tiếp, chẳng hạn vòng 2 của World Cup. Pháp @ Tây Ban Nha Brazin @ Anh Đức @ Ucraina Italia 6 Achentina Cay gia pha Nikolaus Johan I Nikolaus JacobI 1667-1748 1662-1716 1654-1705 Nikolaus II Daniel Johan It Nikolaus JN 1695-1726 1700-1782 1710-1790 1687-1759 Johan IT Jacob IE 1746-1807 1759-1789 Cây gia pha của các nhà toán hoc dong ho Bernoulli Cây phân cấp quần lý hành chính [Ban Giám đốc ị Phòng Phòng Phong Phang Phong Hành chỉnh Tổ chức Tài vụ Kinh doanh Kế hoạch [re] [vantnw] [ II 1 | lÌ | lÌ | 144 Cay thu muc H1 fe] ea) [0800] (3[0000000FlashDisk] ({00KSTNDocum] CH0Baocso] H0BookDown] | {I{0ChuongTrinhCeoDang] [0GiaoTrinh] {300] 1[000TestsProblemForSomeProh] - : Ê3{01-01-2006] kế 3[0AIgorithmic] Cl[0BlumFeraitv] 3[BCombinGeameTheorv] [0DisMotn] CH-¬1[0000DM_Far_Vd] [¬[000Stide] [9501DM_F06] ¬[abutetovị C[Baigiang].

{5[Homework Assignments, UMBC CMSC 441, Fall 2006_files} ([Alan T_ Sherman (Home Page)_files] IICMSC 203 Home Page_tiles] [Cygwin Information and Installation_files] Ciflect2_jim_files] (afLect3_files] {[Form kiem dinh 2007] £[Saoluu] C(t] Cifesct64] [DM] | Cấu trúc của sách Sách Cl 1. : 145 Cây mục lục Book Chapter 1 [Subsection 1. Cay gia pha nguge (Ancestor Tree) Cây phả hệ ngược: mỗi người đều có bố mẹ. Cây này là cây nhị phân (binary tree).

ar] Cây phân hoạch tập hợp es {1,2, 3, 4, 5, 6,7,8, 9, 10} | Tập con các số lết Tập con các số chan: {1,3, 5,7, 9} {2,4,6, 8,10}. {1, 9} Tập con các sé nguyên tb: {2, 4, 8, 10} Tập con số hoàn hảo: {3, 5,7} {6} 4. Các thuật ngữ chính Các thuật ngữ chính liên quan đến cây là: — Niit — node; - Gốc - root; — Lá ~ leaf; — Con — child; ~ Cha — parent; — Té tién —‘ancestors; — Hau dué — descendants: ~ Anh em ~ sibling; — Nut trong = internal node; ~ Chidu cao — hight, chidu sau — depth., n¿ là đấy nút trên cây sao cho n; là cha của nại với 1 < í < &, thì dãy này được gọi là đường đi (padh) từ nút m tới nút my. Độ dài (length) của đường ởi bằng số lượng nút trên đường đi trừ bớt 1.

Như vậy đường đi độ dài 0 là đường đi từ một nút đền chính nó. 147 Nếu có đường đi từ nút ø tới nút b, thì ø được gọi là đổ tiên (ancestor) của b, còn 5 duge goi la hdu dué (descendant) cha a. Trong cay, gộc là nút không có tô tiên chính thường và mọi nút khác trên cây đêu lả hậu duệ chính thường của nó. Một nút không có hậu duệ chỉnh thường được gọi là 14 (leay).

Các nút có cùng cha được gọi là anh em (sibling). Cây con (subiree) của một cây là một nút cùng với tất cả các hậu dué của nó. Chiều cao (heigbi) của nút trên cây bằng độ dài của đường đi đài nhất từ nút đó đến lá cộng 1. Chiều cao của cây (eight oƒa tre) là chiều cao của gốc.

Độ sẩu/mức (depth/level) của nút bằng 1 cộng với độ dài của đường đi duy nhất từ gốc đến nó. root, ancestor internal node parent sibling descendent aikaek ` are leaves Cây con (Subtree) Node and its decendants 148 Đường đi trên cây * Path eo 1 (c ) \, Path 2 G) Path 1: {4,867} Path 2: {d,i} Độ cao (heighO và độ sâu/mức (depth/level) Độ:cao của cây là 5 Tà quan sát cây trong tin học như thế nào? 149 Bậc (Depree) Số lượng con của nút x được gọi là bậc (degree) của x. Ou 3 % vì Saws ay a — A» © @) 4. Cây có thir tw (Ordered Tree) Thứ tự của các nút Các con của một nút thường được xếp theo thứ tự ¿ ái sang phải.

Như vậy bai cây trong hình sau đây là khác nhau, bởi vi hai con của nit a xuất hiện trong hai cây theo thứ tự khác nhau: @) @) OO © Cây với các nút được xếp thử tự được gọi là cây có thứ tự. Ta sẽ xét chủ yếu là cây có thứ tự. Vì vậy, tiếp theo đây thuật ngữ cây là để chỉ cấy có thứ tự. Khi muốn khẳng định không quan tâm đến thứ tự, ta sẽ phải nói rõ là cây không có thứ tự.

Thứ tự "từ trái sáng phải" của các anh em (các con của cùng một nút) có thể tổng quát để so sánh hai nútkhông, có quan hệ tô tiên — hậu duệ. Quy tác 80 ) sánh là: của j. 150 Ví dụ: Nút ¿ ở bên phải nút:b, ở bên trái các nút í,.ƒ ƒ, 2; ø VàẠ không ở bên trái cũng như bên phải của các nút tổ tiên của nó 4, e, e. +: ha vất Xếp thứ tự các nút na Ta có thể xếp thứ tự các nút của cây theo nhiều cách.

Gó ba thứ tự quan trọng nhất, đó là Thứ tự trước, Thú tự sau va Thứ tự gilta (Preorder, Postorđer và Tnorder). Các thứ tự này được định nghĩa một cách đệ quy nhự. sau: " l ~— Nếu cây 7 là rỗng, thì danh sách rỗng là danh sách, theo tứ tự, trước, thứ tự sau và thứ tự giữa của cây 7. — Nếu cây 7 có một nút, thì nút đó chính là danh sách theo thứ tự trước, thứ tự sau và thứ tự giữa của cây 1.

: — Trái lại, giả sử 7à cây có Bốc r với các cây con là 7Ị; Ti. Duyệt theo thứ tự trước — Preorder Traversal” ‘ Thứ tự trước (hay duyệt theo thử tự trước ~ preorder traversal) của các Trút của cây 7là: — Gốc r của T; _ Tiếp đến là các nút của 7¡ theo thứn tự trước; — Sau đó là các nút của 7; theo thứ tự trước; wey ~ Và cuối cùng là các nút của 7 theo thứ tự trước. Duyệt theo thứ tự Sau — Postorder Traversal _ /. Thứ tự sau của các nút của cây Tia: — Cac nut cha 7; theo thir ty sau; — Tiếp đến là các nút của 7; theo thứ tự sau; ~ Các nút'của 7, theo thứ ft sau; ei oe Oe — Sau cùng là nút gốc z.

151 Duyệt theo thứ tự giữa— Inorder Traversal Thứ tự giữa của các nút của cây T là: — Các nút của 7ì theo thứ tự giữa; : =+©'Tiếp đến là núĩ gốc r; -~ ˆ 12 'Tiếp theo là các nữ của Tp, | , Tị, tnỗi nhóm mút được xếp theo thứ tự giữa. Thuật toán duyệt theo thứ tự trước~Preorder Traversal ˆ vald PREORDER (øođeTr) ` f ¬ (1) Đưa rar; (2) for (mỗi con c của z, nếu có, theo thứ-tự từ trái sang) đo PREORDER(); } ` Vi dy: Thứ tự trước của các đỉnh của cây trên hình vẽ là: %bj dể - & hy Ú ƒ G 'Thuật toán duyệt theo thứ tự sau — Postorder Traversal Thuật toán đuyệt theo thứ tự sau thu được bằng cách đảo ngược hai thao tác (1) và (2) trong PREORDER: void POSTORDER ( nođeT z) { for (mỗi con c của r, nếu có, theo thứ tự từ trái sang) do POSTORDER(c) Dua rar; } Vi du: Diy cdc đỉnh được liệt kê theo #lu# tự sạu của cây trong hình vẽ là: bhi gif oda 152 'Thuật toán duyệt theo thứ tự giữa — Inorder Traversal void INORDER (nodeT r) { + jf (r là lá ) Đưa ra r; else { TNORDER(con trái nhật của r); Dua rar; for (mỗi con ơ của r, ngoại trừ con trải nhất, theo thứ tự từ trái sang) do INORDER(c); } Ví dụ: Dãy các đỉnh của cây trong hình vẽ được liệt kê theo thứ tự giữa là: b,a,h, e, Ù G ÿ ƒ 8; d Xếp thứ tự các nút, Để nhớ cách đưa ra các nút theo ba thứ ft vừa trình bày, hãy hình dung là ta đi vòng quanh bên ngoài. bắt đầu từ gốc, ngược chiều kim đồng hồ và sát theo cây nhất. Chẳng hạn, đường đi đó đối với cây trong các ví dụ đã xét ở trên như sau: Đối với thứ tự trước, ta đứa ra nút mỗi khí đi qua nó, ` 'Đối với thứ tự san, ta đưa ra nút khi qua nó ở lần cuối trước khi quay về cha của nó.

Đối với thứ tự giữa, ta đưa ra lá ngay khi đi qua nó, cònn những, nút trong được đưa rà khi lần thứ hai được đi qua. các lá được xếp theo thứ tự từ trái i sang phải như nhau trong cả ba cach sap xép.4, Cây có nhãn (Labeled Tree) Thông thường người ta gán cho mỗi nút của cây một nhãn (2e!) hoặc một giá trị, cũng tương tự như chúng ta đã gán mỗi nút của đanh sách với một phần tử. 153 Nghĩa là, nhãn của nút không phải tên gợi của nút mà là giá trị được cất giữ trong nó. Trong một số ứng dụng, ta có thể thay đổi nhãn của nút mà tên của nó vẫn được giữ nguyên.

Ví dụ: Xét cây có 7 nit m,. Ta gán nhãn cho các nút như sau: — Nút ø có nhãn *; — Nút ø¿ có nhãn +; — Nút ø có nhãn —; — Nút mạ có nhãn 4a; — Nút n; có nhãn ð; = Nút nạ có nhãn a; — Nút mị cô nhãn e. Cây biểu thức (Expression Tree) Cây trong ví dụ vừa nêu có tên gọi là cây biểu thức: (a + b)*(4~ 2) Quy tắc để cây có nhãn biểu diễn một biểu thức là: — Mỗi nút lá có nhãn là toán hạng và chỉ gồm một toán hạng đó. Ví dụ nút 4 biểu diễn biểu thức ø.

— Mỗi nút trong n được gán nhãn là phép toán. Giả sử z: có nhãn là phép toán hai ngôi q, như + hoặc *, con trái biểu điển biểu thúc Z và con phải biểu điễn biểu thức Ey, Khi đó n biểu diễn biểu thức (1) q (Ea). Ta có thể bỏ dấu ngoặc nếu như điều đó là không cân thiết.