Cây là một tập hợp các phần tử (các nút) được tổ chức và có các đặc điểm sau: | CẤU TRÚC DỮ LIỆU CÂY (TREE) Thạc sĩ: HUỲNH PHƯỚC DANH Email: danhhp@ - - KHÁI NIỆM CÂY Cây là một tập hợp các phần tử (các nút) được tổ chức và có các đặc điểm sau: Hoặc là một tập hợp rỗng (cây rỗng). Hoặc là một tập hợp khác rỗng trong đó có một nút duy nhất được làm nút gốc (Root’s Node), các nút còn lại được phân thành các nhóm trong đó mỗi nhóm lại là một cây gọi là cây con (Sub-Tree). Như vậy, một cây con có thể là một tập rỗng các nút và cũng có thể là một tập hợp khác rỗng trong đó có một nút làm nút gốc cây con. - - CÁC KHÁI NIỆM Bậc của một nút: là số cây con của nút đó. 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. Nút nhánh: là nút có bậc khác 0 và không phải là gốc. 2 2 2 1 1 0 0 0 0 - - CÁC KHÁI NIỆM Mức 3 Mức 2 Mức 1 Mức 0 Độ 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. Độ cao của cây: Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất. - - CÂY NHỊ PHÂN Cây nhị phân là cây rỗng hoặc là cây mà mỗi nút có tối đa hai nút con (cây có bậc bằng 2) . Hơn nữa các nút con của cây được phân biệt thứ tự rõ ràng, một nút con gọi là nút con trái và một nút con gọi là nút con phải. Ta qui ước vẽ nút con trái bên trái nút cha và nút con phải bên phải nút cha, mỗi nút con được nối với nút cha của nó bởi một đoạn thẳng. - - CÂY NHỊ PHÂN A B C D E F H G K Root A B C D E F H G K - - CẤU TRÚC DỮ LIỆU CÂY NHỊ PHÂN struct BinT_Node { info; BinT_Node *left; // Vùng liên kết quản lý địa chỉ nút gốc cây con trái BinT_Node *right; // Vùng liên kết quản lý địa chỉ nút gốc cây con phải }; Info Left Right BinT_Node - - DUYỆTCÂY NHỊ PHÂN Duyệt theo thứ tự nút gốc trước (Preorder): Theo cách duyệt này thì nút gốc sẽ được duyệt trước, sau đó mới duyệt đến hai cây con. Căn cứ vào thứ tự duyệt hai cây con mà chúng ta có hai cách duyệt theo thứ tự nút gốc trước: Duyệt nút gốc, duyệt cây con trái, duyệt cây con phải (Root – Left – Right) Duyệt nút gốc, duyệt cây | CẤU TRÚC DỮ LIỆU CÂY (TREE) Thạc sĩ: HUỲNH PHƯỚC DANH Email: danhhp@ - - KHÁI NIỆM CÂY Cây là một tập hợp các phần tử (các nút) được tổ chức và có các đặc điểm sau: Hoặc là một tập hợp rỗng (cây rỗng). Hoặc là một tập hợp khác rỗng trong đó có một nút duy nhất được làm nút gốc (Root’s Node), các nút còn lại được phân thành các nhóm trong đó mỗi nhóm lại là một cây gọi là cây con (Sub-Tree). Như vậy, một cây con có thể là một tập rỗng các nút và cũng có thể là một tập hợp khác rỗng trong đó có một nút làm nút gốc cây con. - - CÁC KHÁI NIỆM Bậc của một nút: là số cây con của nút đó. 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. Nút nhánh: là nút có bậc khác 0 và không phải là gốc. 2 2 2 1 1 0 0 0 0 - - CÁC KHÁI NIỆM Mức 3 Mức 2 Mức 1 Mức 0 Độ 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. Độ cao của cây: Độ dài đường đi từ gốc đến nút lá ở mức thấp nhất. - - CÂY NHỊ PHÂN Cây nhị phân là cây rỗng hoặc .
