Bài giảng Cấu trúc dữ liệu và giải thuật: Cây - TS. Đào Nam Anh

DATA STRUCTURE AND ALGORITHM<br /> Trees<br /> CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT<br /> Cây<br /> Dr. Dao Nam Anh<br /> <br /> Data Structure and Algorithm<br /> <br /> 1<br /> <br /> Resource - Reference<br /> Slides adapted from James B D Joshi,<br /> edit by Dao Nam Anh.<br /> Major Reference:<br /> <br /> •<br /> <br /> Robert Sedgewick, and Kevin Wayne,<br /> “Algorithms” Princeton University, 2011, Addison<br /> Wesley<br /> <br /> •<br /> <br /> Algorithm in C (Parts 1-5 Bundle)- Third Edition<br /> by Robert Sedgewick, Addison-Wesley<br /> <br /> •<br /> <br /> Cấu trúc dữ liệu và giải thuật, Đinh Mạnh Tường.<br /> <br /> •<br /> <br /> Giải thuật và lập trình, Lê Minh Hoàng, Đại<br /> Học Sư Phạm, 2002<br /> <br /> Data Structure and Algorithm<br /> <br /> 2<br /> <br /> Tree - Cây<br /> A<br /> <br /> E<br /> <br /> B<br /> C<br /> <br /> D<br /> G<br /> <br /> F<br /> <br /> I<br /> H<br /> <br /> Data Structure and Algorithm<br /> <br /> 3<br /> <br /> Tree - Cây<br /> <br /> •<br /> <br /> •<br /> <br /> Cây là một cấu trúc<br /> dữ liệu gồm một tập<br /> hữu hạn các nút,<br /> giữa các nút có một<br /> quan hệ phân cấp<br /> gọi là quan hệ "cha<br /> - con".<br /> Có một nút đặc biệt<br /> gọi là gốc (root).<br /> <br /> A<br /> <br /> E<br /> <br /> B<br /> C<br /> <br /> D<br /> G<br /> <br /> F<br /> <br /> I<br /> H<br /> <br /> Data Structure and Algorithm<br /> <br /> 4<br /> <br /> Tree - Cây<br /> <br /> •<br /> <br /> Có thể định nghĩa<br /> cây bằng các đệ quy<br /> như sau:<br /> <br /> A<br /> <br /> Mỗi nút là một cây,<br /> nút đó cũng là gốc<br /> của cây ấy<br /> <br /> E<br /> <br /> B<br /> C<br /> <br /> D<br /> G<br /> <br /> F<br /> <br /> I<br /> H<br /> <br /> Data Structure and Algorithm<br /> <br /> 5<br /> <br />