19. Trình bày khái niệm cấu trúc dữ liệu cây và cây nhị phân? Phương pháp lưu trữ cây nhị phân ? Cho ví dụ minh hoạ ?

            -Cây là 1 kiểu cấu trúc dữ liệu phi  tuyến có nhiều ứng dụng trong thiết kế giải thuật. Khái niệm phi tuyến ở đây được hiểu theo nghĩa khi duyệt các dữ liệu không theo 1 trình tự nhất định từ trên xuống dưới mà có thể lặp lại.

            Cây là 1 kiểu cấu trúc dữ liệu bao gồm 1 tập hợp các thành phần theo cấu trúc thứ bậc đều xuất phát từ 1 đỉnh gọi là gốc. Trong thực tế chúng ta gặp rất nhiều hình ảnh cấu trúc dữ liệu cây, VD tổ chức các đvi hành chính, gia phả hệ gia đình….

            Khi biểu diễn cây ta có 3 phương pháp :

            +p21: Dùng cấu trúc thứ b ậc

            +pp2: Topo ( bao đóng)

            +pp3: Giải tích

            Một tính chất rất quan trọng của cấu trúc dữ liệu hình cây là tính chất đệ quy. Tức là mỗi 1 vị trí nào đó luôn luôn có thể coi là đỉnh hoặc là nút phụ thược vào các nút khác.

            -Cây nhị phân : là 1 trường hợp đặc biệt của cây tổng quát và có mức độ ứng dụng thông thường cao hơn cây tổng quát. Cây nf có 2 nhánh : nhánh phải ( cây con phải) và nhánh trái ( cây con trái)           

            …..

            Trong TH cây nf chỉ có nhánh phải or trái được gọi là cây nf không đầy đủ. Từ 1 cây nf ko đầy đủ cta có thể bổ sung thêm các nút trống để được cây nf đầy đủ về mặt hình thức.

            Trong TH nếu chỉ có all các nhánh phải or all các nhánh trái ở all các bậc thì cta có cây nf đặc biệt glaf cây nf suy biến. Khi đó cta có thể lần lượt bổ sung thêm các nút trống để có cây nf đầy đủ

            …….

            - Phương pháp lưu trữ cây nhị phân :

              2 dạng : mảng – dsach liên kết

            +pp1 : trong th1, người ta lần lượt đánh số các nút của cây nf từ trái qua phải theo thứ tự tăng dần từ 1 trở đi sau đó lưu trữ ll các nút vào các thành phần của mảng thêo p2 kế tiếp

                        ……

            ……

            Trong pp lưu trữ này khi biết 1 nút con thứ I nào đó ta dễ dàng xd được 2 nút con bên trái và phải của nó là 2i và 2i+1

            Như vậy thêo pp lưu trữ ằng mảng, cta dễ dàng xd được 2 nút bên trái và phải cuẩ bất kì 1 nút nào đó. Dvs cây nhị phân ko đầy đủ cta phải bổ sung thành cây nf đầy đủ trước khi đánh số và tiến hành lưu trữ để không có sựu nhầm lẫn cây con với cây gốc

            +pp2: trong trường hợp này, mỗi nút của cây nf được lưu trữ dưới dạng ds liên kết với 2 nút con bên trái và bên phải

                        Lchild   data      Rchild

            Nếu nút con bên trái hoặc bên phải là rỗng thì nhánh bên trái or bên phải sẽ được biểu diễn        Xdata               dataX

VD:…..

            Như vậy khi biểu diễn cây nf dù là dưới dạng 1 ma trận hay 1 dslk bao gồm 3 phần là L child, data và R child thì bươc đầu tiên người ta phải làm là bổ sung thành 1 cây nf đầy đủ đảm bảo thứ bậc của cấu trúc dl hình cây vì dvs kiểu ctruc dl phi tuyến này vấn đề không phải là dl chứa trong các nút mà vấn đề quan trọng là thứ bậc của các nút đó.