tailieunhanh - CẤU TRÚC DỮ LIỆU - CÂY

Tham khảo tài liệu 'cấu trúc dữ liệu - cây', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chương 3. CÂY Trong chương này chúng ta sẽ nghiên cứu mô hình dữ liệu cây. 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ư đượ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 các 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 và 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 biểu diễn cây và sự thực hiện các phép toán cơ bản trên cây. Sau đó chúng ta sẽ nghiên cứu kỹ một dạng cây đặc biệt đó là cây tìm kiếm nhị phân. . Một số khái niệm . Các định nghĩa - Cây là một tập hợp hữu hạn các phần tử mỗi phần tử gọi là một nút Node 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 Mức 3 Mức 4 A nút gốc A là nút cha của B C D B C D là các nút con của A - Cây rỗng cây không có nút nào cả - Cấp của nút số nút con của nó vd nút B có cấp là 2 - Cấp của cây cấp lớn nhất của các nút có trên cây. Cây có cấp n gọi là cây n phân ví dụ cây trên là cây tam phân - Lá nút có cấp là 0 ví dụ các là F C G J - Mức Nút gốc có mức là 1. Nút cha có mức i thì nút con có mức i 1 - Chiều cao của cây mức lớn nhất trên cây ví dụ cây trên có chiều cao 4 - Nút trước nút sau Nút x là nút trước của nút y nếu cây con gốc x có chứa nút y khi đó y là nút sau của nút x. ví dụ D là nút trước của nút J - Đường đi path Dãy nút u1 u2 . . . uk mà nút bất kỳ Ui là cha của nút Ui 1 thì dãy đó là đường đi từ nút U1 đến nút uk - Độ dài đường đi số cạnh có trên đường đi ví dụ dãy DHJ là đường đi từ nút D đến nút J với độ dài là 2 - Cây có thứ tự ordered tree là cây mà nếu ta thay đổi vị trí của các cây con thì ta có một cây mới. Như vậy nếu ta đổi các nút bên trái và bên phải thì ta được một .