tailieunhanh - Chương 3 Cây - Phần 1

Cây gồm một tập hợp hữu hạn các nút-node Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root). Cây không có nút nào gọi là cây rỗng. | CHƯƠNG 3- CÂY Chương 3: Cây Các khái niệm cơ bản Cây nhị phân Định nghĩa và tính chất Biểu diễn cây nhị phân Duyệt cây nhị phân CÁC KHÁI NIỆM CƠ BẢN Khái niệm cây: Cây gồm một tập hợp hữu hạn các nút-node Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root). Cây không có nút nào gọi là cây rỗng. CÁC KHÁI NIỆM CƠ BẢN Bậc – degree – của một nút là số con của nó. Nút lá (leaf) –terminal node – là nút không có con, bậc của nút lá bằng 0. Ngược với nút lá là các nút có con, gọi là nút phân nhánh hay nút trung gian (internal node). Bậc của cây là bậc cao nhất của các nút trong cây. Cây nhị phân là cây bậc 2. Nếu cây có bậc cao hơn 2 ta gọi là cây nhiều nhánh. CÁC KHÁI NIỆM CƠ BẢN Mức – level – là đẳng cấp của nút trong mô hình phân cấp. Quy ước nút gốc có mức 1, nếu nút cha có mức i thì nút con có mức i + 1. Chiều cao – height – hay con gọi là chiều sâu – depth – là mức lớn nhất của nút trên cây. Đường đi – path – từ nút p đến nút q trên một cây là dãy nút p = n1,n2, ,nk = q sao cho ni là cha của ni+1. CÁC KHÁI NIỆM CƠ BẢN Độ dài đường đi – path length – là số cung nối từng cặp hai nút trên đường đi, nó chính là số nút trừ 1. Cây có thứ tự - ordered tree – là cây mà có xét đến thứ tự giữa các con của một nút. Nói nôm na là có xét đến quan hệ “anh em”. Con trưởng hay con cực trái là một nút là con thứ nhất trong quan hệ thứ tự giữa các nút cùng cha. Em liền kề của một nút là nút đứng ngay sau trong quan hệ thứ tự giữa các nút cùng cha. Rừng – forest- là danh sách hữu hạn cây. CÂY NHỊ PHÂN Định nghĩa và tính chất. Biểu diễn cây nhị phân. Duyệt cây nhị phân ĐỊNH NGHĨA VÀ TÍNH CHẤT Cây nhị phân là cây bậc 2, một nút có nhiều nhất là hai con. Cây nhị phân là cây có xét đến thứ tự, phân biệt con thứ nhất, con thứ hai gọi là con trái và con phải. Ba cây nhị phân này có cùng | CHƯƠNG 3- CÂY Chương 3: Cây Các khái niệm cơ bản Cây nhị phân Định nghĩa và tính chất Biểu diễn cây nhị phân Duyệt cây nhị phân CÁC KHÁI NIỆM CƠ BẢN Khái niệm cây: Cây gồm một tập hợp hữu hạn các nút-node Có một quan hệ thứ tự bộ phận (cha-con) giữa các nút. Có một nút đặc biệt, không là con của bất cứ nút nào và là tổ tiên của mọi nút trong cây, gọi là nút gốc (root). Cây không có nút nào gọi là cây rỗng. CÁC KHÁI NIỆM CƠ BẢN Bậc – degree – của một nút là số con của nó. Nút lá (leaf) –terminal node – là nút không có con, bậc của nút lá bằng 0. Ngược với nút lá là các nút có con, gọi là nút phân nhánh hay nút trung gian (internal node). Bậc của cây là bậc cao nhất của các nút trong cây. Cây nhị phân là cây bậc 2. Nếu cây có bậc cao hơn 2 ta gọi là cây nhiều nhánh. CÁC KHÁI NIỆM CƠ BẢN Mức – level – là đẳng cấp của nút trong mô hình phân cấp. Quy ước nút gốc có mức 1, nếu nút cha có mức i thì nút con có mức i + 1. Chiều cao – height – .