tailieunhanh - Giáo trình Cấu trúc dữ liệu và giải thuật: Phần 2 - An Văn Minh, Trần Hùng Cường

Nối tiếp nội dung phần 1, phần 2 giáo trình "Cấu trúc dữ liệu và giải thuật" trình bày một dạng cấu trúc dữ liệu phi tuyến; mô tả, thiết kế và đánh giá các giải thuật sắp xếp và tìm kiếm thông dụng, cũng như vấn đề cài đặt các giải thuật này trong bài toán ứng dụng. | Chuong 4 CAY Trong chuang nay chiing ta se nghien curu mo hinh du lieu cay tree . Cay la mot cau true phan cap tren mot tap hop nao do cac doi tugng. Mot vi du quen thupc ve cay do la cay thu muc hoac muc luc cua cuon sach cung la mot cay. Cay dugc sir dung rong rai trong rat nhieu van de khac nhau. Chang han no dugc ap dung de to chuc thong tin trong cac he co so du lieu de mo ta cau true cii phap ciia cac chuong trinh nguon khi xay dung cac chuong trinh djeh. Rat nhieu bai toan ma ta gap trong cac Imh vuc khac nhau dugc quy ve vice thuc hien cac phep toan tren cay. Trong chuong nay chiing ta se trinh bay djnh nghTa cac khai niem co ban ve cay. Chung ta cung se xet cac phuong phap cai dat cay va thuc hien cac phep toan co ban tren cay. Sau do ta nghien emr ky mot so dang cay dac biet do la cay nhj phan tim kiem va cay can bang. . CAY VA CAC KHAI NIEM C O BAN . Djnh nghTa D jn h nghTa I Mot cay la tap hgp huu h cac nut trong do co mgt niit dac biet ggi la goc root . Giua cac nut co moi quan hp phan cap ggi la quan he cha-con. D jn h nghTa 2 Cay dugc djnh nghTa de quy nhu sau - Mgt nut la mgt cay va nut nay cung la goc ciia cay. - Gia sir T T2 . T n gt 1 la cac cay co goc tuong img ri r2 . r . Khi do cay T voi goc r dugc hinh thanh bang each cho r tro thanh nut cha cua cac niit ri r2 . rn. 131 . Mot so khai niem cd ban - B a c c m m p t nuf. la so con cua nut do. - B g c cu a m ot cay la bac cua mit c6 bac Ion nhat tren cay do so cay ccot toi da cua mot nut thupc cay . Cay c6 bac n thi goi la cay n - phan. - N u t gdc la nut khong c6 nut cha. - N iit Id la nut c6 bac bang 0. - N iit nhdnh la nut c6 bac khac 0 va khong phai la niit goc. - Mice cu a m g t nut Muc g6c To 1 Goi T . Ti. T la cac cay con cua To. Khi do Muc T Muc T2 . Muc T Muc To 1 - C h ieu cao cu a cay la muc ciia nut c6 muc Ion nhat c6 tren cay do. - D u o n g di Day cac nut ni n2 . nk dupe goi la dubmg di neu ni la cl cua ni i 1 lt i lt k-1 . - D g d d i cu a d uem g di la so nut tren .