Tree Data Structure

Learnabout Tree Data Structure with AR e-BookCreate by Kobkaew MeepianManagement Information System SSRU

โครงสรา้ งขอ้ มลู แบบต้นไม้โครงสรา้ งข้อมลู แบบต้นไม้ เป็นโครงสร้างไมเ่ ชงิ เส้น (Non Linear) มีลกั ษณะคล้ายกิ่งก้านต้นไม้แตกก่ิงก้านออกไป เชน่เดียว กบั ธรรมชาติของขา่ วสารข้อมลู ต้นไม้แตกก่ิงจากลา่ งไปบน แตโ่ ครงสร้างข้อมลู ในคอมพวิ เตอร์จะกลบั หวั รากอยบู่ นก่ิงอยู่ด้านล่าง จดุ ท่ีแตกกิ่งออกไป เรียกว่าโหนด (Node)ขา่ วสารเก็บอย่ทู ่ีโหนด ! จดุ เช่ือมโหนดเรียกวา่ ลิงค์(Link)นิ ยามโครงสร้างต้นไม้ มีโหนดพเิ ศษเรียกวา่ รากหรือรูต(root node), R โหนดอื่น ๆ ที่ไมใ่ ช่รูต ถกู แบ่งย่อยออกเป็น n กลมุ่ แต่ละกล่มุ ไมม่ ีโหนดร่วมกนั เลย แต่ละกลมุ่ ก็เป็นต้นไม้เหมือนกนั แต่เรียกว่าเป็นต้นไม้ยอ่ ย(Sub tree)โครงสรา้ งต้นไม้• R คอื รตู โหนดของตน้ ไมย้ อ่ ย A,B,C,D• A คอื รตู โหนดของต้นไมย้ อ่ ย E, F, G• F คอื รตู โหนดของต้นไมย้ อ่ ย J• แBลคะอื Iรตู โหนดของตน้ ไมย้ อ่ ย H

โครงสรา้ งข้อมลู แบบต้นไม้ระดบั ของโหนด (Level) แสดงถึงระยะทางตามแนวด่ิงว่าโหนดนัน้ ห่างจากรตู โหนดเท่าไร ถา้กาํ หนด ให้รตู โหนดเป็นระดบั 1 (บางท่ีกาํ หนดให้รตู โหนดเป็นระดบั 0) ให้นับระยะห่างบวกระดบั ของรตู โหนด เช่น3 + 1 (หรอื 3 + 0) เป็ นต้นระดบั ของโหนด R คือรตู โหนด ระดบั 1 A,B,C,D คือโหนดระดบั 2 E,F,G,H,I คือโหนดระดบั 3 J คือโหนดระดบั 4ดีกรีของโหนด (Level Degree)คือจาํ นวนต้นไม้ย่อยของโหนดนัน้ A มีดีกรีเป็ น 3 B มีดีกรีเป็ น 2 F มีดีกรีเป็ น 1 C,D,E,G,H,I,J มีดีกรีเป็ น 0โหนดที่เป็ นใบ (Leaf Node)โหนดทมี่ ดี กี รเี ป็ น 0 ส่วนโหนดทมี่ ดี กี รมี ากกวา่ 0 เรยี กวา่โหนดภายใน (interior/branch node)• A,B,F เป็ นโหนดภายใน• C,D,E,G,H,I,J เป็ นโหนดใบ

ความสมั พนั ธข์ องโครงสร้างต้นไม้ ความสัมพนั ธข์ องโครงสรา้ งตน้ ไม้ กาํ หนดให้โหนดราก (Root)คอื จดุ ยอด V0 และ x, y, z เป็ นจุดยอดในตน้ ไมแ้ ละ (V0 , V1 , ….,Vn )เป็ นทางเดนิ ในตน้ ไมจ้ ะกลา่ ววา่ 1) Vn-1 เป็ น บดิ ามารดา (Parent) ของ Vn2) V0,…,Vn-1 เป็ น บรรพบรุ ุษ (Ancestor) ของ Vn 3) Vn เป็ น ลกู(Child) ของ Vn-1 4) ถา้ x เป็ นบรรพบุรุษของ y จะไดว้ า่ y เป็ น ผู้มาทหี ลงั(Descendant) x 5) ถา้ x และ y เป็ นลกู ของ z จะไดx้ และ y เป็ น พน่ี ้องกนั(Siblings) 6) ถา้ x ไมม่ ลี กู x จะเป็ น จุดยอดทส่ี ้ินสดุ (Leaf Node) หรอื ใบไม้7) ถา้ x ไมใ่ ช่จุดยอดทสี่ ้ินสดุ x จะเป็ น จุดยอดภายใน (Internal vertex)หรอื กง่ิ 8) กราฟยอ่ ยของ T ประกอบดว้ ยจุดยอด x และโหนดทมี่ าทหี ลงั นบัจากบรรพบรุ ษุ ของมนั ทง้ั หมด โดยมโี หนด x เป็ นราก และเรยี กวา่ ตน้ ไมย้ อ่ ยของตน้ ไมท้ มี่ รี าก x

ป่ า (Forest) โครงสรา้ งตน้ ไมท้ นี่ ําเอา โหนดราก (Root) ออกไปเหลอื เฉพาะตน้ ไมห้ รอื กง่ิ ของ โครงสรา้ งต้นไมน้ ้นั ๆโครงสร้างต้นไมแ้ บบทวิภาค (Binary Tree) ต้นไมท้ มี่ โี หนดราก (Root) และทกุ จุดยอดอาจมลี กู (Child) ทางซ้าย, ลกู ทางขวา, ลกู ทางซ้ายและลกู ทางขวา หรอื ไมม่ ลี กู เลย โครงสรา้ ง ต้นไมท้ วภิ าคแบบสมบรู ณ์ (Complete Binary Tree) คอื โครงสรา้ งตน้ ไมท้ วภิ าคทที่ ุก จุดยอดมลี กู ทง้ั สองดา้ นหรอื ไมม่ ี ลกู เลย

โครงสร้างต้นไมท้ วั ่ ไป (General Trees) เซตจาํ กดั T ทมี่ สี มาชกิ เรยี กวา่ โหนด ซ่งึ ประกอบดว้ ยคุณลกั ษณะ ดงั นี้ 1. T เป็ นต้นไมว้ า่ ง (Null Tree หรอื Empty Tree) หรอื 2. T มสี มาชกิ พเิ ศษ คอื โหนด R อยหู่ น่ึงโหนดทเ่ี รยี กวา่ Root Node 3. สมาชกิ ทเี่ หลอื ของ T อาจประกอบดว้ ยต้นไมย้ อ่ ยทม่ี จี าํ นวน สมาชกิ เป็ นศนู ยห์ รอื มากกวา่ ไดแ้ ก่ T1, T2 , …, Tทการแทนโครงสรา้ งต้นไม้ การแทนความสัมพนั ธท์ เี่ กดิ ขนึ้ จากรปู โครงสรา้ งตน้ ไมด้ ว้ ยรปู ทสี่ ามารถประมวลผลดว้ ย คอมพวิ เตอร์ ซ่งึ แบง่ ออกเป็ น 2 วธิ ี ไดแ้ ก่1. การแทนโครงสรา้ งต้นไมด้ ้วยโครงสร้างอารเ์ รย(์ Array) การแทน โครงสร้างตน้ ไมด้ ว้ ยโครงสร้างอารเ์ รยจ์ ะตอ้ งใช้อารเ์ รยอ์ ยา่ งน้อย 3 ชุด สําหรบั เป็ น ทเี่ ก็บของขอ้ มลู และพอยนเ์ ตอรท์ ช่ี ไี้ ปยงั โหนดลกู ทาง2. กดา้านรแซท้ายนแโคละรดงสา้ นรา้ขงวตา้นไม้ทวิภาค (Binary Trees) การแทนดว้ ยอารเ์ รยจ์ ะ ใช้อารเ์ รยท์ ขี่ นานกนั จาํ นวน 3 ชุด คอื INFO, LEFT และ RIGHT และ ตวั แปร ROOT ถา้ ให้K คอื ตาํ แหน่งของโหนดจะไดค้ วามสัมพนั ธ์ดงั นี้1. INFO [K] เก็บส่วนทเี่ ป็ นขอ้ มลู ของโหนด N2. LEFT [K] เก็บตาํ แหน่งของ Left ของโหนด N3. RIGHT [K] เก็บตาํ แหน่งของ Right Child ของโหนด N4. ROOT เก็บตาํ แหน่งของ Root ของตน้ ไม้ T



โครงสรา้ งต้นไม้แบบTHREADED TREEดาํ เนนิ กกาารรแนบําบไรบานยากราที รรเชมี อื่กี มารโปยงรบั ปโรดงุ ยแมกกี ไ้ าขรโเพดยม่ิ วธิ โกี หานรดพเิ ศษทRNแลoเ่ีoระodยี กteกาํ ขวหแอา่ ลนงะดทพโใรหอหี ยน้HนดEเ์นAตําDอรเท์(ปH็านeงพaซอd้ายeยrนขNเ์ อตoงอdรeH์ )eทไaช่ีวdท้ไี้ eปจ่ี rดุยNเงั รoม่ิ dHตe้นeจaขะdอชeงไี้rปTยงั

แบบประเมนิ ความพงึ พอใจในการใช้AR-Book