Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây (tree). Cây là một cấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc về cây, đó là cây thư mục hoặc mục lục của cuốn sách cũng là một cây. Cây được sử dụng rộng rãi trong rất nhiều vấn đề khác nhau. | Giáo trình - Cấu trúc dữ liệu và Giải thuật Bài 21 CÂY TỔNG QUÁT Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây tree . Cây là một cấu trúc phân cấp trên một tập hợp nào đó các đối tượng. Một ví dụ quen thuộc về cây đó là cây thư mục hoặc mục lục của cuốn sách cũng là một cây. Cây được sử dụng rộng rãi trong rất nhiều vấn đề khác nhau. Chẳng hạn nó được áp dụng để tổ chức thông tin trong các hệ cơ sở dữ liệu để mô tả cấu trúc cú pháp của các chương trình nguồn khi xây dựng các chương trình dịch. Rất nhiều bài toán mà ta gặp trong các lĩnh vực khác nhau được quy về việc thực hiện các phép toán trên cây. Trong chương này chúng ta sẽ trình bày định nghĩa các khái niệm cơ bản về cây. Chúng ta cũng sẽ xét các phương pháp cài đặt cây và thực hiện các phép toán cơ bản trên cây. Sau đó ta nghiên cứu kỹ một số dạng cây đặc biệt đó là cây nhị phân tìm kiếm và cây cân bằng. . Định nghĩa Định nghĩa 1 Một cây là tập hợp hữu hạn các nút trong đó có một nút đặc biệt gọi là gốc root . Giữa các nút có một quan hệ phân cấp gọi là quan hệ cha con . Định nghĩa 2 Cây được định nghĩa đệ qui như sau 1. Một nút là một cây và nút này cũng là gỗc của cây. 2. Giả sử T1 T2 . T n 1 là các cây có gốc tương ứng r1t r2 . rn. Khi đó cây T với gốc r được hình thành bằng cách cho r trở thành nút cha của các nút r1t r2 . rn . Các khái niệm về cây Bậc của một nút là số con của nút đó Bậc của một cây là bậc lớn nhất của các nút có trên cây đó số cây con tối đa của một nút thuộc cây . Cây có bậc n thì gọi là cây n - phân nút gốc là nút có 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à nút gốc Mức của một nút Mức gốc To 1 Gọi T1 T2 . Tn là các cây con của To. Khi đó Mức T1 Mức T2 . Mức Tn Mức To 1 Chiều cao của cây là số mức lớn nhất có trên cây đó Đường đi Dãy các đỉnh n1 n2 . nk được gọi là đường đi nếu ni là cha của ni 1 1 i k-1 Độ dài của đường đi là số nút trên đường đi -1 Cây được sắp Trong một cây nếu các cây con của mỗi đỉnh được .
