Bài giảng Cấu trúc dữ liệu và giải thuật: Cây nhị phân được biên soạn gồm các nội dung chính sau: tổng quan về cây nhị phân; thao tác trên cây; các loại cây; cây nhị phân; duyệt cây nhị phân. Mời các bạn cùng tham khảo! | KHÁI NIỆM CƠ BẢN Cây là một cấu trúc phân tầng của các phần tử gọi là nút node Mỗi node chứa một phần tử đơn. Mỗi phần tử có thể có 1 hoặc nhiều nhánh kết nối với các nút khác được gọi là nút con. Mọi cây có 1 nút gốc root duy nhất. Mọi nút trừ nút gốc đều là con của một nút khác nút cha. 3 3 KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC CÂY TRONG THỰC TẾ Thông thường các mô hình tổ chức sẽ có cấu trúc cây Một cây tổ chức là một cây không có thứ tự có cấu trúc phân tầng như tổ chức của phòng ban trong thương mại. University Engineering Medicine Science Education Law Arts Chemistry Physics Maths Languages History 4 4 KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC CÂY TRONG THỰC TẾ Sơ đồ phân loại sinh học cũng là một loại cây phổ biến. Cây này cũng không có thứ tự nhưng có tổ chức phân lớp. animals worms insects arachnids vertebrates stars sponges ants beetles flies fish reptites birds mammals snakes lizards crocodiles 5 KHOA CÔNG NGHỆ THÔNG TIN CẤU TRÚC CÂY TRONG THỰC TẾ Tổ chức file và các thư mục Chúng tả có thể mô hình hóa tổ chức các file bằng cách dùng cây không sắp xếp theo mô hình nút lá và các thư mục như các nút cha. root doc bin lib etc tmp users cp grep sort mail motd passwd 6 KHOA CÔNG NGHỆ THÔNG TIN Thao tác trên cấu trúc cây Nó phải có thể truy cập vào nút gốc của cây truy cập tất cả các tổ tiên của một nút trong cây truy cập tất cả con cháu của một nút trong cây thêm một nút mới vào cây xóa một nút nhất định khỏi cây Duyệt cây. 7 KHOA CÔNG NGHỆ THÔNG TIN Một số định nghĩa 8 KHOA CÔNG NGHỆ THÔNG TIN Một số định nghĩa Cây có thể được sắp xếp hoặc không được sắp xếp. Cây không có thứ tự cây là cây ở hình dạng. Theo nghĩa cấu trúc nó trông giống như một cái cây. Đối với bất kỳ nút nhất định nào không có thứ tự nào được áp đặt cho các nút con của nút đó 9 KHOA CÔNG NGHỆ THÔNG TIN Một số định nghĩa Một cây có thứ tự áp đặt thứ tự trên các nút Có nhiều chiến lược sắp xếp thứ tự nhưng theo nghĩa đơn giản nhất thứ tự có thể được áp đặt bằng cách gán các số khác nhau cho các nút con
