Tiểu Luận BÁO CÁO KHOA HỌC_Cấu trúc đống và ứng dụng_cây nhị phân

I. Lí do chọn đề tài.

Hiện nay, công nghệ thông tin với tốc độ phát triển rất nhanh. Các nhà khoa học khẳng định rằng chưa có một ngành khoa học - công nghệ nào lại có nhiều ứng dụng như công nghệ thông tin. Việc ứng dụng công nghệ thông tin vào trong giáo dục đã trở thành mối ưu tiên hàng đầu của nhiều quốc gia trong đó có Việt Nam.

Trong quá trình học các giải thuật nói chung và môn cấu trúc dữ liệu nói riêng, chúng ta rút ra một nhận định chung là: nhiều giải thuật phức tạp trừu tượng, khó hiểu, khó hình dung vấn đề. Do đó chúng ta luôn mong muốn trong quá trình học giải thuật nên có những mô phỏng trực quan để chúng ta có thể tiếp thu giải thuật một cách dễ dàng hơn. Tuy nhiên, việc học tốt giải thuật có rất nhiều thận lợi dó là giúp cho quá trình tư duy giải thật tốt hơn, phát hiện vấn đề nhanh hơn, đặc biệt giúp cho việc học các môn học khác có tính logic cao được thuận lợi hơn. Nhưng để học tốt giải thuật thì không dễ dàng với nhiều người. Vậy để giúp người học tiếp thu một cách dễ dàng các giải thuật thì phải xây dựng các phần mền mô phỏng thuật toán.

Cấu trúc đống có rất nhiều ứng vào các giải thuật nhưgiả thuật sắp xếp đống, vào hàng đợi ưu tiên. Nghiên cứu cấu trúc đống để hiểu thêm về nó phục vụ trong việc giải quyết các bài toán

Phần 2:Nội Dung

Chương 1 : Cơ sở lý thuyết về cây nhị phân.

I. Định nghĩa và các ví dụ

1. Định nghĩa.

Cây là một cấu trúc phi tuyến tính. Một cây (tree) là một tập hữu hạn các nút trong đó có một nút đặc biệt gọi là nút gốc (root), giữa các nút có một mối quan hệ phân cấp gọi là quan hệ “cha - con”.

Có thể định nghĩa cây một cách đệ quy như sau:

1. Một nút là một cây. Nút đó cũng là gốc của cây ấy.

2. Nếu T1, T2, ., Tn là các cây, với n1, n2, . nk lần lượt là các gốc, n là một nút và n có quan hệ cha - con với n1, n2, . nk thì lúc đó một cây mới T sẽ được tạo lập, với n là gốc của nó. n được gọi là cha của n1, n2, . nk ; ngược lại n1, n2, . nk được gọi là con của n. Các cây T1, T2, ., Tn được gọi là các cây con (substrees) của n.

Ta quy ước : Một cây không có nút nào được gọi là cây rỗng (null tree).

Có nhiều đối tượng có cấu trúc cây.

2.Ví dụ .

a) Mục lục của một cuốn sách, hoặc một chương trong sách, có cấu trúc cây.

b) Biểu thhức số học x + y * (z – t) + u/v, ta có thể biểu diến dưới dạng cây như hình 1.