Kỹ thuật lập trình - Chapter 6

Tài liệu tham khảo giáo trình kỹ thuật lập trình gồm 6 chương - Chương 6 các thuật toán trên cấu trúc câY (Tree)
Nội dung trích xuất từ tài liệu:
Kỹ thuật lập trình - Chapter 6 105Kü thuË t lË p tr× nhCH¬NG 6 c¸c thuËt to¸n trªn cÊu tróc c©Y (Tree) C© y lµ mét cÊ u tróc d÷ liÖ u rÊ t th«ng dông vµ quan träng trong nhiÒ u ph¹ mvi kh¸ c nhau cña kü thuË t m¸ y tÝ nh. VÝ dô : Tæ chøc c¸ c quan hÖ hä hµ ng trong mét gia ph¶ , môc lôc cña métcuèn s¸ ch, x© y dùng cÊ u tróc vÒ có ph¸ p trong c¸ c tr× nh biª n dÞch. Trong ch ¬ng tr× nh nµ y, chóng ta kh¶ o s¸ t c¸ c kh¸ i niÖ m c¬ b¶ n vÒ c© y, c¸ cphÐp to¸ n trª n c© y nhÞ ph© n, còng nh c¸ c phÐp to¸ n trª n c© y nhÞ ph© n c© n b» ng( AVL tree) vµ øng dông cña hai lo¹ i c© y nhÞ ph© n t× m kiÕ m (BST), c© y nhÞ ph© nc© n b» ng ( AVL tree).I. Ph©n lo¹i c©y: I.1. Mét sè kh¸i niÖ m c¬ b¶n: 1. C©y: C© y lµ tË p hîp c¸ c phÇ n tö gäi lµ nót, mét nót (t ¬ng tù nh métphÇ n tö cña d∙ y) cã thÓ cã kiÓ u bÊ t kú. C¸ c nót ® îc biÓ u diÔ n bëi 1 ký tù ch÷,mét chuçi, mét sè ghi trong mét vßng trßn. Mét sè ®Þnh nghÜ a theo ®Ö quy ( Mét nót ®¬n còng chÝ nh lµ mét c© y. ( C¸ c nót ® îc gäi lµ ë cïng mét c© y khi cã ® êng ®i gi÷a c¸ c nót nµ y. ( Mét c© y sÏ bao gåm mét nót gèc (Root) vµ m c© y con, trong mçi c© y con l¹ i cã mét nót gèc vµ m1 c© y con nhá h¬n v.v. ( Mét c© y kh«ng cã mét nót nµ o c¶ gäi lµ c© y rçng. VÝ dô 1 : - A lµ nót gèc víi 3 c© y con lÇ nNuùt goác 1 A l ît cã 3 nót gèc riª ng lµ ø B, C, D - Nót cha (ancestor) 2 B C D Nót con (descendent) A lµ nót cha cña B, C, D G, H lµ nót con cña C 3 G H E F G, H kh«ng quan hÖ cha con víi A 4 I J K H× nh 5.1. C© y víi nót gèc lµ A 106Kü thuË t lË p tr× nh VÝ dô 2 : Víi ®Ò c ¬ng mét m«n häc T, ta cã thÓ biÓ u diÔ n d¹ ng c© y nhsau : T CH ¬NG I I.1 I.2 CHÖÔNG I CHÖÔNG III CHÖÔNG II CH ¬NG II II.1 I.1 I.2 II.1 II.2 II.3 II.1.1 II.1.2 II.2 II.1.1 II.1.2 II.3 H× nh 5.2 CH ¬NG III 2. Nót cha (Ancestor) : Nót ®øng trª n cña mét nót ® îc gäi lµ nót cha C lµ nót cha cña G, H Nót con (descendent) : Nót ®øng sau mét nót kh¸ c ® îc gäi lµ nót con cñanót ®ã. Nót I, J, K lµ nót con cña nót E 3. BËc (degree) : - BË c cña nót lµ sè c© y con cña nót ®ã. C cã bË c lµ 2, E cã bË c lµ 3 (H× nh 5.1) - BË c cña c© y lµ bË c lín nhÊ t cña c¸ c nót trong c© y. C© y trong h× nh 5.1 cã bË c lµ 3. C© y bË c n ® îc gäi lµ c© y n ph© n nh c© y nhÞ ph© n, c© y tam ph© n. 4. Nót l¸ vµ nót trung gian: - Nót l¸ lµ nót cã bË c b» ng 0 (tøc lµ kh«ng cã c© y con nµ o) : - Nót trung gian: lµ mét nót cã bË c kh¸ c 0 vµ kh«ng ph¶ i lµ nót gèc. VÝ dô : Trong h× nh 5.1, B, G, H, I, J, K, F lµ nót l¸ C, D, E lµ nót trung gian. 5. Møc cña nót (level) : Nót gèc cã møc lµ 1 Møc cña nót con = møc cña nót cha + 1 107Kü thuË t lË p tr× nh VÝ dô : trong h× nh 5.1, ...