---
title: โครงสร้างข้อมูลและอัลกอริทึม 23/08/2565
subtitle: 
date: วันอังคารที่ 23 สิงหาคม 2565  เวลา 13.00 น.
---

								(ข้อความสดจากระบบถอดความเสียงพูดทางไกล)


(อาจารย์สุธาสินี) คราวนี้นะคะ ก่อนที่เราจะขึ้นเรื่องใหม่ เดี๋ยวครูจะทวนของนะคะ ที่เราเรียนผ่านกันมา จะมี 2 เรื่องนะคะ stack กับ qeue Stack กับคิวนะคะ จะมีลักษณะจัดเก็บข้อมูลคล้าย ๆ กัน ถ้าเราเข้าใจ stack เราก็น่าจะเข้าใจ qeue นะคะ มันจะมองในมุมตรงกันข้ามกัน คราวนี้ ถ้าเราดูว่าStack เป็นอย่างไร ตามหัวข้อที่ครูลิสต์มาให้ qeue ตามที่เราเปรียบเทียบกัน มีความแตกต่างกันอยู่นะ แต่เราต้องจับประเด็นให้ได้ว่าอะไรที่มันหัวข้อเดียวกันแล้วความต่างแต่ละตัวมันเป็นอย่างไร เราเริ่มต้นที่ stack นะคะ ถ้าเราพูดถึง Stack ลักษณะของการจัดเก็บข้อมูลก็คือ เข้าก่อนออกทีหลัง เข้าก่อนออกทีหลังนะคะ ถ้าเราอยากจะนึกเป็นภาพนะ ว่าเอ๊ะลักษณะของการเข้าก่อนออกทีหลังเป็นอย่างไร ให้ทุกคนนึกถึงหลอดใส่ CD ข้อมูลที่อยู่ใต้น่ะ อยู่อันแรกสุดเลย จะอยู่ด้านล่างใช่ไหมคะ ข้อมูลที่เอาเข้าไปเก็บในหลอดซีดีอันสุดท้ายน่ะ มันจะอยู่ด้านบนสุด เวลาเราดึงออกมาใช้ เราก็ดึงข้างบนน่ะดึงออกมาใช้ทีละตัว เพราะฉะนั้น ตัวที่เก็บล่าสุดจะเอาออกมาใช้งานก่อนนะคะ ก็จะเข้า Concept ของ Stack คือเข้าก่อนออกทีหลัง หรือชามก๋วยเตี๋ยวเหมือนกันเขาล้างเสร็จเขาก็ตั้งชั้นขึ้นมาใช่ไหม เวลาเรามาซื้อเขาก็จะหยิบออกมา หยิบออกมานะคะ แล้วคำสั่งที่เราใช้ใน Stackมีอะไรบ้าง เรามีคำสั่งอยู่แค่ 2 ตัว ที่ใช่ใน stack คือ push กับ pop Push คือใส่เข้าไป เรา Push ใส่เข้าไปนะคะ ส่วน Pop ก็คือดึงออกมานะ เรา pop ก็คือดึงข้อมูลออกมาจาก Stack นะคะ เวลาเราจัดเก็บข้อมูลใน Stack ให้นึกถึง List นะคะ ให้นึกถึง List ให้นึกถงเป็นตาราง ให้นึกถึงลักษณที่เป็นลักษณะที่เป็นตารางนะคะ Push ก็คือค่อย ๆ ใส่ช้อมูลเข้าไปทีละช่อง ทีละช่อง แล้วเวลา pop Pop ก็คือข้อมูลไหนที่เราใส่ล่าสุดน่ะ เมื่อเราสั่ง Pop มันจะถูกเอาออกมาทำงานก่อนแล้วตัวกำกับหรือตัวชี้ว่าข้อมูลล่าสุดที่อยู่ใน Stack มันอยู่ตรงไหน ใช่ไหมคะ Stack มันมีทางเข้าทางออกเพียงแค่ 1 ทางเท่านั้น เพราะฉะนั้น มันจะมีม Top นะคะ ตัว Top นี่ เป็นตัวบอกว่าข้อมูลล่าสุด ที่อยู่ใน Stack มันอยู่ใน Indeที่เท่าไร เพราะฉะนั้น Top จะเป็นตัวบอกตำแหน่งว่าข้อมูลล่าสุดที่อยู่ในตำแหน่งนี่ มันอยู่ตำแหน่งที่ Index ที่เท่าไหร่ ถ้าดราวาดเป็นตาราง 1 แถว หลายคอลใช่ไหมคะ Index ก็คือช่องแรกเราจะหมายเลขช่อ คือ 0 12 3 ไล่ไปเรื่อย ๆ เพราะฉะนั้น หมายเลข Index นั่นล่ะ คือตัว Top ที่บอกว่าตัวล่าสุดมันอยู่ช่องไหนนะคะถ้า stack ว่าง หมายถึงอะไร เราไม่มีข้อมูลอยู่ใน Stack เลย เพราะฉะนั้น ค่า Top จะเป็นเท่ากับ -1 คือไม่ได้บอกเลยว่าอยู่ช่องที่เท่าไรเลย แต่จะเริ่มต้นที่ 0 นะคะ -1 นะคะ แล้วมาดูอีก 1 ตัว คือ qeue แล้วอันนี้จะใกล้ตัวเรามากขึ้น เหมือนกับที่เราไปต่อคิวซื้อข้าว ไปต่อคิวทำกิจกรรมต่าง ๆต่าง ๆ que เข้าก่อน ก็ต้องออกก่อน เพราะฉะนั้น qeue จะมีทางเข้าออกอยู่ 2 ทางนะคะ ออกข้างหน้า เข้าข้างหลังนะคะ คิว มีทางเข้าทางออก 2 ทาง เข้าข้างหลังออกข้างหน้าใช่ไหม คนมาก่อน ก็ต้องออกข้างหน้า เวลาเข้า ก็คือเข้าข้างหลังนะคะ เหมือนเราไปต่อคิวน่ะ มันมีทางเข้าทางออกกันคนละทางคำส่งที่ใช้ในคิวมีอยู่ 2 ตัวเหมือนกัน เข้า กับเอาเข้ากับเอาออกเหมือนกันนะคะ เราจะใช้คำสั่ง Enqeue Enqeue Enter คิวนะคะ ส่วน Deque ก็คือเอาออก deqeue ก็คือเอาข้อมูลออก มันก็จะตรงกับ Push กับ Pop คิวก็คือ Enqueue แล้วตัวกำกับข้อมูลที่อยู่ใน qeue เราใช้ค่าอะไรเป็นตัวกำกับคิวเราก็มองเป็นลิสต์เหมือนกัน เป็นช่อง ๆ หมายเลขช่อง เราเริ่มต้นหมายเลขช่องแรกก็คือ 0 ตัวกำกับจะมี 2 ตัวนะคะ ก็คือ fromt กับ rear front คือข้างหน้า rear คือข้างหลัง คือ F กับ Front จะเป็นตัวบอกข้อมูลว่าตัวไหนที่จะถูกเอาออก เพราะมันเอาออกข้างหน้านะคะ จะชี้อยู่ด้านหน้า เป็นตัวบอกว่า front กำกับอยู่ที่ช่องไหน ถ้าข้อมูงนั้นจะถูกเอาออก ส่วน rear จะเป็นตัวกำกับอยู่ที่ทางเข้านะคะ rear จะบอกตำแหน่งล่าสุดของข้อมูลว่า ข้อมูลตัวที่เข้าล่าสุดใน queue อยู่ที่ตำแหน่งไหน ก็ระบุค่า index ก็คือหมายเลขช่องที่ค่าข้อมูลนั้นอยู่ คิวว่าง คิวว่าง แสดงว่ามันว่างนะ queue ว่าง ก็คือไม่มีข้อมูลอยู่ใน queue เลย front กับ rear จะมีค่าเป็น -1 นะคะ front กับ พำหพเป็น -1 โอเค อันนี้ครูทบทวนให้นะ สรุปมาให้ว่า Stack กับ queue เป็นอย่างไร คราวนี้ก่อนที่จะขึ้นเรื่องใหม่ ครูมีแบบฝึกหัด ลองทำดูว่าเข้าใจหรือเปล่า ครูจะค้างหน้านี้เอาไว้ให้นะคะแจกคนละชุดนะคะ นะคะหรือสามารถเปิดในสมุดได้นะคะ คราวที่แล้วน่ะ ที่เราทำไปนะในเรื่องของ Queue นะ เราก็ไปทบทวน ไปทบทวนได้ ก่อนจะขึ้นเรื่องใหม่ ลองดูนะคะ ว่าเรายังจำได้ไหมนี่ front Stack กับ Queueดูนะคะ ครูมีอยู่ทั้งหมด 5 ข้อด้วยกัน ทำลงในกระดาษที่ครูแจกเลย เขียนลงไปในนี้เลยนะคะ ข้อ 1 กับข้อ 2 ให้เขียนอธิบายนะคะ ว่าลักษณะของ Stack เป็นอย่างไร ลักษณะของ Queue เป็นอย่างไร คำสั่ง Push 5 หมายถึงอะไร ครูระบุไว้ให้แล้วนี่ Push หมายถึงอะไร เรา Push ข้อมูลอะไรลงไป ก็เขียนอธิบาย คำสั่งนี้ทำอะไร คำสั่ง Pop ทำอะไร ถัดมา ก็จะมากำหนดค่า Top ครูมี Stack ให้แล้วเมื่อเราใช้คำสั่ง Push แล้วนี่ ค่า Top จะมีค่าเป็นอะไรหลังจากใช้คำสั่ง Pop แล้วค่า Top จะเป็นอย่างไรนะคะ Queue ก็เหมือนกัน เริ่มต้น เขียนชื่อลงในกระดาษแผ่นแรกนะคะ 

(อาจารย์สุธาสินี) คราวนี้มาดูเห็น...มาดูพร้อมกันนะคะ ตัวนี้คือ Stack นะ F0mpM8i^นะคะ Stack คือเข้าข้างหลัง ออกข้างหลังใช่ไหมคะ Stack นะเข้าข้างหลัง ออกข้างหลัง ก็คือทางเข้าทางออกอยู่ด้านหลังนะคะ คำสั่งตัวแรกดู ครูสั่งอะไรคะ PusPush คือใส่ ครู Puอะไรคะ ครู Push เลข 3 คำสั่งคือใส่ ข้อมูลเลข 3 เพราะฉะนั้น ครุใส่ตรงไหน ใส่ข้างหลังเห็นไหมคะ ครูใส่เลข 3 เห็นไหมคะ ครูใส่เลข 3 ลงมาลงมา มันมีที่ว่างตรงไหนคะ ครูหาทีว่างใส่นะ นี่ครูเจอช่องนี้ว่างพอดีเลย เพราะฉะนั้น เลข 3 ครูก็อยู่ที่ช่องนี้นะคะ เลข 3 นี่ครูมาอยู่ที่ช่องสุดท้าย มันมีช่องใส่อยู่ช่องเดียวน่ะ ข้างหน้ามันเต็มหมดแล้ว แล้วค่า Top จะเป็นอะไรค่า Top เป็นอะไร เราก็ต้องดูสิว่าค่าเลขช่องนี้มันอยู่ช่องหมายเลขอะไร เราก็ต้องเริ่มเขียนจากช่องปรก็คือ หมายเลขหมายเลข 3 หมายเลข 4 ถูกไหมคะ เพราะฉะนั้นแล้วนี่ ข้อมูลของครูอยู่ช่แงหมายเลขอะไร หมายเลข 4 เพราะค่า Top จึงมีค่าเท่ากับ 4 เห็นไหมคะ มันตรงกันนะ ข้อมูลครุอยู่ตรงนี้ ครูมัคือ 4 Top ครูเลยมีค่าเท่ากับ 4 คำสั่ง Push นะคะ เดี๋ยวเรามาดูอีก 1 ตัว ดูสิคะ Push เหมือนกัน เห็นไหมคะ เจอ Pusแสดงว่าใส่ข้อมูลใช่ไหม Push คือใส่ข้อมูล ใส่ข้างไหน คือ ใส่ข้างหลัง แล้วก็ใส่ลงมานะคะ คือ ใส่หมายเลข 10 พอครูใส่หมายเลข 10 เห็นไหม มันมีที่ว่างมันค่อย ๆ ไหลลงมา ไหลลงมา นะคะ ก็เลยมาใส่ที่ช่องหลังเลข 3 แล้วหมายเลขช่องคืออะไร เราก็เขียนเหมือนเดิม 0 1 2 เพราะฉะนั้น ค่า Top เลยมีค่าเท่ากับ 2 เห็นไหมคะ เพราะข้อมูลของเรานี่ อยุ่หมายเลข 2โอเค ถัดมา เราเจอคำสั่งใหม่แล้ว คำสั่ง Pop Pop คือเอาข้างหลังออกออก เอาข้อมูลที่อยู่ข้างหลังออก คือ pop เพราะฉะนั้น ข้อมูลที่อยู่ข้างหลังคือเลข 9 ใช่ไหมคะ ข้อมูลที่อยู่ข้างหลังตัวหลังสุดคือเลข 9 ไม่ใช่ค่ะ คือ เลข 4 พูดผิด ตัวหลังสุด คือ เลข 4 เพราะฉะนั้น ครูเอาเลข 4 ออก ถูกไหมคะ ลบมันทิ้งไปเลย ครูลบมันทิ้ง Pop คือเอาออก เพราะฉะนั้น มันจะไม่มีข้อมูลหมายเลข 4 อยู่ใน stack ของเราแล้ว เพราะฉะนั้น ข้อมูลตัวล่าสุดของเรา เลขอะไรคะ เลข 9 ถ้าเลข 9 เราอยู่ที่หมายเลขช่องอะไร เราไม่รู้เราก็เขียน 0 1 2 เพราะฉะนั้น ค่า pop ก็คือ ค่า 2 นะคะ อันไหนที่เราตัดทิ้งเราก็ลบออกไปเลย ถัดมา เรา pop อีกแล้ว pop คืออะไรคะ เอาออก เราก็เขียนไว้ก่อนนะ Pop คือเอาออก เอาตรงไหนออก มันเหลือตัวเดียวน่ะ มันมีเลข 7 ตัวเดียว เพราะฉะนั้น เราต้องเอาเลข 7 ออก เพราะฉะนั้น ตอนนี้เรามีข้อมูลใน stack ไหม จะเป็น 0 ได้ไหม ไม่ได้ ถุกไหมคะ เป็น 0 ไม่ได้ ถูกไหมคะ เพราะฉะนั้นTop ของเราจึงมีค่าเป็น -1 ตามที่ครูบอกนะ stack ว่าง มีค่าเป็น -1 โอเคเราลองมาดู queue queue queue เห็นไหมคะ ครูบอกแล้วตัวนี้คือ Queue ครูก็บอกแล้วว่า อันนี้ คือ queue จะมีตัวกำกับหรือตัวชี้อยู่ 2 ตัว ก็คือ front กับ rear คือ f กับ r ใช่ไหมคะ Front  อยู่ข้างหน้าrear อยู่ข้างหลัง จะมีคำสั่ง enqueue กับ dequeue  ใช่ไหมคะ dequeue คืออะไร เอาออก dequeue คือ เอาข้อมูลออก เอาข้างหน้าออก เห็นไหมคะDequeue คือ เอาข้างหน้าออก เพราะฉะนั้น เอาเลขอะไรออกคะ เลข  7 เอาเลข 7 ออก เพราะฉะนั้น ข้อมูลตัวแรกคืออะไร เราเขียนหมายเลขก่อนข้อมูลตัวเลขจะอยู่ที่เลข 6 ใช่ไหม มันตรงกับเลขอะไร ช่อง 1 ก็คือ front ก็คือข้างหน้าถูกไหม ตัวสุดท้ายอยู่ช่องเลขอะไร เลข 3 นะคะ อันนี้คือตัวแรก อันนี้คือตัวแรก อันนี้คือตัวสุดท้าย ถัดมา ครูใช้คำสั่ง enqueue เราเห็น Enqueue  ว่ามีตัวเลขใช่ไหมคะ แสดงว่าต้องเอาเข้าน่ะ เอาเข้าถูกนะ เอาเข้าข้างหน้าหรือข้างหลัง ข้างหลังเอาเลข 3 เข้า ถูกไหมคะ พอครูเอาเลข 3 เข้า จะไปอยู่เลขไหนจะอยู่หลังหมายเลข 6 เราใส่เลขกำกับก่อน 0 1 2 ข้อมูลตัวแรกอยู่ที่ไหนคะ 0 ข้อมูลตัวสุดท้ายอยู่ที่ 2 front บอก front จะบอกข้อมูลตัวแรกใช่ไหมคะ ส่วน rear จะบอกข้อมูลตัวสุดท้าย ถัดมา Enqueue  เอาเข้าเอาออก เอาเข้า เอาเข้าข้างหลัง เอาอะไรคะ เอา 8 เข้า เพราะฉะนั้น มันจะไปอยู่ที่ช่องหลังเลข 4 มันมีหมายเลขช่องไหม มี ข้างหลัง ก็คือ rear ใช่ไหม 8 อยู่หมายเลข 3 ตัวแรก อยู่ช่องหมายเลข 1 เห็นไหมคะ อันนี้คือช่องแรก อันนี้คือช่องสุดท้ายถัดมา dequeue คืออะไรคะ เอาออก เอา...เอาข้างหน้าออกใช่ไหมคะ เพราะฉะนั้น เอาหมายเลขอะไรออก หมายเลข 4 เพราะฉะนั้น ข้อมูลจะเหลือแค่ 1 ตัว เพราะฉะนั้นอยู่ช่องอะไรคะหมายเลข 2 มีข้อมูลอยู่แค่ตัวเดียวเห็นไหมคะ หมายเลขช่อง ก็คือเลข 2 ถัดมาDequeue Dequeue คืออะไรคะ เอาออกอีกแล้ว เอาอะไรออก เอา 2 ออก ตอนนี้มีอะไรใน queue ไม่มี เพราะฉะนั้น จะมีค่าเป็น -1 คือ queue ว่าง เมื่อกี้เราใช้คำสั่ง enqueue  กับ เพราะฉะนั้น Endqueue 5 หมายถึงอะไรคะ เอาข้อมูลเลขอะไร เอาข้อมูลเลข 5 เข้าไปใน queue ใช่ไหมคะ dequeue คืออะไร เอาข้อมูล ทำไมคะ ออกจาก queue โอเค ถ้า Push คือ เอาข้อมูลอะไร เอาข้อมูล 5 ใส่ลงไปใน Stack5 มาจากไหนนี่นะ มันบอกนี่ คำสั่งมันบอกว่าเอาเลข 5 นะคะ ส่วน Pop คืออะไรคะ เอาข้อมูลออกจาก Stack เอาข้อมูลข้างหลังหรือข้างหน้าออก Stack เอาข้อมูลข้างหลังหรือข้างหน้าออก ข้างหลัง ถูกไหมคะ เอาข้อมูลข้างหลังออก เอาข้อมูลจากข้างหลังนะคะ ออก เดี๋ยวถ่ายรูปนะคะ ลงใน classroom หน่อย ถ่ายรูปแบบฝึกหัดที่ทำนะคะ ลงใน Classroomเสร็จแล้วทุกคนถ่ายรูปนะคะ แล้วก็โพสต์ลงไปใน classroom ถ่ายให้ครบ 3 แผ่นเลยนะ มี 4 คน ทุกหน้าคุณแม่ เสร็จแล้วเดี๋ยวครูให้เบรก 5 นาทีนะ เดี๋ยวมาขึ้นเรื่องใหม่นะคะ จะให้เบรกก่อนจะได้เคลียร์ของเก่า โอเค มาต่อนะคะ มาต่อนะคะ จะเป็นอีก 1 โครงสร้างนะ เราพูดถึง Stack กับ Queue ไปแล้วนะคะ Stack กับ qมันข้อมูลมันจะเรียงกันเป็นแถว อาจจะเป็นแนวตั้งหรือแนวนอนก็ได้ แต่ทีนี้ ถ้ามีข้อมูลนะคะ ที่มันไม่ได้จัดเก็บเป็นแนวข้อมูลหรือเชิงโครงสร้าง เป็นแนวตั้งหรือแนวนอนนะคะ เป็นแนวตั้ง แนวนอน แต่ข้อมูลเรานะคะ มีลักษณะการจัดเก็บเป็นลำดับชั้น แล้วเราจะเก็บข้อมูลแบบไหน เราก้จะมีรูปแบบนะคะ แบบแรกเราจะเรียกว่า "โครงสร้างข้อมูลแบบต้นไม้" แล้วก็มีอีก 1 แบบนะคะ ที่จัดเป็นแบบเชื่อมโยงเครือข่ายได้นะคะ คือ กราฟกับต้นไม้นะ เราเรียนต้นไม้ก่อน เสร็จแล้วเราจะมาเรียนกราฟ ลักษณะของโครงสร้างข้อมูลแบบต้นไม้ จะเหมือนกับ folder จะลักษณะเหมือนกับ Folder เลย มีตัวแม่ คลิกเข้าไปก็มีลูก ถูกไหมคะ คลิกเข้าไปก็มีตัวลูก เรื่อย ๆ นะ คราวนี้ในการจัดเก็บข้อมูลโครงสร้างข้อมูลแบบต้นไม้นะคะ เดี๋ยวเราลองจินตนาการนะ ต้นไม้นะคะ เดิม รากมันจะอยู่ด้านล่าง ถูกไหม ต้นไหมที่เราปลูกต้นไม้มันจะอยู่ด้านล่าง เรากลับดึงแรก ขึ้นมาไว้ข้างบนนะคะ ลักษณะแบบนี้ ตัวบนสุดก็คือ รูทโหนด ก็คือตัวพ่อแม่เลยน่ะ คือ รูต ถ้าเทียบกับบรรพรุต ทุกคนนึกภาพโครงสร้างบรรพบุรุษที่อยู่ในบ้านเราได้นะ เราจะมีบตั้งต้นแล้วก็มีลูกหลายแตกแขนงมาเรื่อย ๆ นะคะ ลักษณะแบบเดียวกัน บนสุด คือ บรรพบุรุษ โหนดคือต้นกำเนิดเลย แต่รูตโหนดเรามีอยู่แค่ 1 โหนดเท่านั้นนะคะ ตัววงกลจะเรียกว่า "โหนด" ตัวกลม ๆ จะเรียกว่า "โหนด" เสร็จแล้วนี่ นี่คือบรรพบุรุษถูกหรือเปล่า บรรพบุรุษนี่ ก็มีลูก เห็นไหมคะ บรรพบุรุษก็มีลูก ลูกก็มีหลานออกมาใช่ไหมคะ กลุ่มนี้ คือ พี่น้องนะ คือพี่น้องที่มีพ่อเดียวกัน กลุ่มนี้นะคะ ด้านซ้ายกับด้านหขวาเป็นลูกพี่ลูกน้อง ใช่ไหม ลูกพี่ลูกน้อง อันนี้คือพ่อเรา อันนี้... คือลูกพี่ลูกน้องเราโอเค ตัวที่อยู่ล่างสุดนะคะ ตัวที่อยู่ล่างสุด เราจะมีชื่อเรียกว่า ลิสต์โหนด ก็คือเราเป็นรุ่นยังไม่มีใครต่อจากเรา เรายังไม่ได้แต่งงานถูกไหมคะ เราจะเปรียบเป็นลีฟโหนดของตระกูลนะ เป็นคนล่างสุด เป็นคนชั้นสุดท้าย ล่ของตระกูลนะคะ เราจะเห็นว่าลักษณะของโครงสร้างข้อมูลแบบนี้เราเห็นเป็นลำดับชั้นถูกไหมคะ อันนี้เป็นชั้นที่ 1 ชั้นที่ 2 ชั้นที่ 3 ไล่ลงมาเรื่อย ๆ นะคะ โอเค ตัวบนสุด เรียกว่า "root node root คือ root node คือโหนดแม่ตัวล่างสุดเรียกว่า "leนะคะ คือ ลีฟโหนด คือ ตัวสุดท้าย จะเห็นว่าลีฟโหนด มี 7 มี 9 มี 15 มี 45 แล้วก็ 77 พวกนี้ที่อยู่ล่างสุดนี่เรียกว่า "left node" ทั้งหมดเลย ข้างบน ข้างบนเลข 7 คือ พ่อนะ แม่นะคะ เราเรียกพ่อนะ พ่อของ 7 คือ 13 ลูกของ 13 คือ 7, 915 นะคะ พ่อของ 13 คืออะไร 23 โอเค คราวนี้ จากตรงนี้นะคะ เราดูการเรียกชื่อ หรือว่าลำดับของการเรียกชื่อ โหลด 23 มันอยู่บนสุดเราจะเรียกว่า มันคือ รูตโหนด ตัวนี้นะคะ โหนดที่อยู่บนสุด ก็คือ root nodeตัวนี้นะคะ นะคะ เพราะว่ามันคือโหนดแรกสุดนะ ถัดมาโหนด 23 นี่ เชื่อมไปยังโหนด 13 กับ 54 นะคะมันเป็นพ่อของ 13 กับ 54 นะ มันเป็นพ่อของ 13 กับ 54 เสร็จแล้ว 13 กับ 54 นี่เป็นลูก เป็นลูกของ 23 นะคะ 7 9 15 โหนด 7 โหนด 9 โหนด 15 เป็นลูกของโหนด 13 ลิฟโหนดคือโหนดล่างสุดของต้นไม้นะ โหนดที่อยู่ด้านล่างสุดของแต่ละกิ่งของต้นไม้ไม่มีอะไรต่อลงไปอีกแล้ว เราเรียกตัวนั้นว่า leaf node นะคะเห็นไหม เริ่มต้น รูตโหนด คือ 23 นะคะ คราวนี้ระดับของโหนด ก็คือลำดับชั้นของโหนดน่ะ เราเริ่มที่ลำดับชั้นของนะคะ ลำดับชั้นของต้นไม้นะคะ เราเราเริ่มต้นที่ 0 เพราะฉะนั้น ตัวบนสุด จะอยู่ระดับ 0 นะคะ 15... 3 กับ 54 จะอยู่ระดับ 1 ระดับ 2 ระดับ 3 ไล่ลงมาเรื่อย ๆ โหนดพ่อ พ่อก็คืออยู่สูงกว่าตัวเอง เห็นไหม ลูกก็คือ ณ โหนดที่กล่าวถึงพ่อก็คืออยู่ระดับสูงขึ้นไป ลูกก็คืออญุ่1 ชั้นนะคะ โหนดพี่น้อง จะเป็นพี่น้องกันได้ต้องพ่อเดียวกัน 7, 9, 15 เพราะมีพ่อเดียวกันถูกไหม เพราะมีพ่อเดียวกันแต่ 46 กับ 77 ก็เป็นพี่น้องกันถูกไหมคะ พ่อเดียวกัน เป็นลูกพี่ลูกน้องกันนะ เป็นญาติกัน เป็นลูกพี่ลูกน้องกันลีฟโหนด ก็คือโหนดล่างสุดไม่มีอะไรทิ่มลงไปแล้ว ไม่มีอะไรแตกออกมาอีกแล้ว โหนดนี้ ไม่มีอะไรแตกออกมาอีกแล้ว มันสุดท้ายแล้ว ส่วน ดีกรี ดีกรีคือจำนวลูกทั้งหมดของโหนดที่กล่าวถึง เช่น ดีกรีของ 46 คืออะไร คือ 1 ดีกรีคือจำนวนลูก ดีกรีคือจำนวนลุกนะคะ 46 มีลูกอยู่ 1 13 มีลูกอยู่ 3 47 มีลูกไหมคะ ไม่มี 77 มีลูกไหม ไม่มี เพราะฉะนั้น ดีกรีมีค่าเป็นอะไรคะ เป็น 0มีกระดาษไหม หยิบกระดาษให้ครูหน่อย ครูมีรูป ครูมีรูปนี้นะคะ เขียนด้านหลังกระดาษที่ครูให้ไปก็ไตอบให้ครูหน่อย ... นี่ ตอบอะไรเอ่ย วาดรูปก่อนนะ แล้วก็ตอบว่าข้อ 1 โหนดคืออะไร ข้อ 2 ข้อ 3 ข้อ 4 ข้อ 5ใครมีสมุด ทำลงสมุดนะคะ วาดรูปด้านซ้ายก่อน แล้วก็เขียนตอบด้านขวา ลอกโจทย์ด้วยนะ เช่นระดับของโหนด 30 คือ... ตอบมา อันนี้ครูก๊อป

(ปี้) ก๊อปฯคำอธิบายมาให้นะคะ จะได้เห็นด้วย root node คืออะไร ระดับของโหนดคืออะไร ดีกรีคืออะไร คราวนี้ดู ดูอีกทีหนึ่งนะ ดูอีกทีหนึ่งนะ ในโหนดนะคะ ที่ครูให้ เดี๋ยวนะจากต้นไม่นะคะ ที่เราเห็นต้นนี้นะ จากต้นไม่ต้นนี้ ที่เราเห็น 1 ต้นนี่ ถ้าเราพูดถึงพ่อนะคะ พ่อ แสดงว่าคนที่อยู่สูงกว่าเรา พ่อของเรานี่ แสดงว่าลำดับชั้นนี่จะอยู่สูงกว่าถูกไหมคะ ลูกของเราจะต้องอยู่ต่ำกว่าเรานะคะ  อย่างเช่น 55 นะคะ ครูพูดถึง 55 พ่อของ 55 คืออะไร พ่อก็อยู่ข้างบนถูกไหมคะ ก็คือ 50 ถูกไหม อันนี้คือพ่อ55 คือ ลูกของ 50 ถูกไหมคะ ลูกของ 50 ถูกไหมคะ แล้วลูกของ 55 คืออะไรคะ 52 อันนี้คือลุก เห็นไหมคะเราพูดถึงโหนดนี้ เราพูดถึงโหนด 55 พ่อของ 55 คืออะไร คือ 50 ลูกของ 55 คืออะไร 52 เห็นไหมคะ มันอยู่ด้านล่างนี่คือลูก ถัดมา พ่อของ 70 แสดงว่ามันต้องอยู่ข้างบนใช่ไหม คืออะไร คือ 40 ใช่ไหมคะ พ่อของ 70 คือ 40 แล้วลูกของ 70 คืออะไร พี่น้อง หมายถึงพี่น้องพ่อเดียวกัน พี่น้องคือพี่น้องพ่อเดียวกัน พี่น้องของ 20 คืออะไร 70 เพราะอะไร เพราะมีพ่อเดียวกัน เดียวกันนี่ไง เพราะมีพ่อเดียวกัน ถึงเป็นพี่น้องกันโจทย์ข้อแรก รูตโหนด รูตคืออะไรคะ ตัวบนสุดรูตคือตัวบนสุดใช่ไหมคะ ตัวบนสุดคืออะไร 40 ถถูกไหมคะ บนสุดคือ 40 พ่อของ 50 พ่อ แสดงว่าดูข้างบนนะ พ่อของ 50 คืออะไร 70นะคะ พ่อของ 50 ก็อยู่ด้านบน ถูกเปล่า อยู่ด้านบนตัวเองน่ะ ตัวเองเชื่อมมาจากเส้นอะไร ก็คือ 70 ถัดมา ลีฟโหนด คือ โหนดที่ไม่มีลูก ก็คือไม่มีอะไรต่อท้ายลงไปแล้ว โหนดที่ไม่มีอะไรต่อท้ายตัวเอง คือไม่มีลูกน่ะมันสิ้นสุดที่ตัวเอง มันไม่มีอะไรไปต่อท้ายแล้ว เพราะฉะนั้น ลีฟโหนดเรามีกี่ตัว 3 ตัว ก็คืออะไรคะ 30, 45แล้วก็ 52 ก็คือตัวที่ไม่มีลูกน่ะ ไม่มีลูกนี่ ไม่มีลูก อันนี้ก็ไม่มีลูกถัดมา พี่น้อง พูดถึงพี่น้องต้องพ่อเดียวกัน พี่น้องของ 45 คืออะไรคะ 55 เพราะอะไร เพราะพ่อเดียวกัน เดี๋ยวนะนี่ไง พี่น้องของ 45 ก็คือ 55 เพราะมันพ่อเดียวกันไง พ่อ คือ 50 ต่อนะคะพี่น้องของ 50 นี่ดูสิ 50 มีพ่อคือ 40 ใช่หรือเปล่า มีพ่อคือ 70 มีพี่น้องไหม ไม่มี ไม่มีพี่น้องนะคะ เป็นลูกคนเดียว หรือขีด - ไม่มีพี่น้อง เป็นลูกคนเดียวนะคะถัดมาระดับของ 30 คืออะไร ระดับคืออะไรคะชั้น ลำดับชั้นจากรูตโหนด โดยเริ่มต้นที่ 0 ชั้นนี้มีระดับเป็น 0 ใช่ไหมคะ ชั้นนี้ระดับเป็น 1 ชั้นถัดมาระดับเป็น 2แล้วก็เป็น 3 30 อยู่ระดับไหนคะ ระดับ 2 55 ดีกรีคืออะไรคะ จำนวนลูก มีลูกกี่คน 55 มีลูกกี่คน คนเดียวนะคะ นี่ไง 55 มีลูกกี่คน มีลูกคนเดียวนะคะ เห็นไหมก็ตอบ 1 ดีกรีของ 55 คือ 1 คือ 1 ดูนะคะ ครูให้วาดต้นไม่เครือญาตินะ สมชายเป็นต้นตระกูล สมชายอยู่บนสุด สมชายมีลูก 2 คน คือ A กับ B A มีลุก 1 คน ชือ cB มีลูดอีก 3 คน ชื่อ D E F และ F ก็มีลูก 1 คน ชื่อ Z วาดต้นไม้เครือญาติให้ครูหเราเริ่มต้นถูกไหมคะ ต้นตระกูลของคือใคร คือ สมชาย เพราะทุกคนต้องมีสมชายเป็นจุดเริ่มต้นนะคะ เป็นต้นตระกูลของบ้านน้อย สมชายมีลุกกี่คน2 คน ใช่ไหมช่วยครูวาดต่อหน่อย คือ A กับ B เราวาดต่อให้ครูหน่อย A มีลูก 1 คน ชื่อ Cชื่อ C สมชายมีลูก 2 คน คือ A กับ B ใช่ไหมคะ A มีลูกกี่คน มีลูก 1 คน ใช่ไหมคะ ก็ลากต่อจาก A ใช่ไหมคะเพราะมันเป็นลูฏของ A น่ะ มาลากออกเป็นลูกคนอื่นไม่ได้ เราก็วาดออกจาก A เพราะ A มีลูก 1 คน B มีลูกกี่คน 3 คน เพราะฉะนั้น ต้องมีกี่เส้น 3 เส้นนะคะ เห็นไหม ครูก็มีเส้นจาก B 3 เส้นนะคะ วาดลูกก่อน ลูกคนแรกชื่อ D, E แล้วก็F ใช่ไหมคะ คนอื่นไม่มีลูกเลยนะ D กับ E ไม่มีลูกเลย แต่ F คนเดียวที่มีลูกใช่ไหมคะ ก็คือ Z อันนี้เครือญาติของบ้านสมชายใช่ไหมคะ เป็นแบบนี้ ครูถามต่อ จากรูปนี้ รูตโหนดคืออะไรคะ รูตโหนดคืออะไร ก็คือโหนดที่ชื่อสมชาย ถูกไหม ก็เขาอยู่บนสุด เขาเป็นต้นตระกูลของบ้านหลังนี้ ลิฟโหนดคืออะไรคะลีฟโหนด ลีฟโหนด คือโหลดที่มีลูกไหม เพราะฉะนั้น อันไหนที่ไม่มีลูก C, D,E แล้วก็ Z เห็นไหมคะ คนเหล่านี้เป็นโสด ถ้าเทียบนะ คนเหล่านี้เป็นโสดยังไม่ได้แต่งงานเลยนะคะ ยังเป็นโสดอยู่ไม่มีลูกพี่น้องของ D คือใคร พี่น้องของ D มีใครบ้าง D DoD Dog พี่น้องของ D. Dog มีใครบ้าง E กับ F ใช่ไหมคะ พี่น้องของ D DogC มีพี่น้องไหมคะ C มีพี่น้องไหม ไม่มี C ไม่มีพี่น้องนะคะ C ไม่มีพี่น้อง Z มีพี่น้องไหมไม่มีเป็นลูกคนเดียวเหมือนกัน Z ก็เป็นลูกคนเดียว โอเคจากเครือตรงนี้ใช่ไหมคะ เราวาดได้ต้นไม้ 1 ต้นนะ ถัดมา ต้นไม้นี่ ในต้นไม้นะคะ เราสามารถมีต้นไม้ย่อย ที่อยู่ภายในต้นไม้ได้เช่น จากรูปนี้ ตรงนี้ ฝั่งซ้ายของ 23 ย่อยนะ ของ 23 ฝั่งขวาตรงนี้ ก็คือต้นไม้ย่อยนะคะ เห็นไหม เพราะว่ามันมีกิ่งก้านสาขาแตกลงมา ตรงนี้ก็เลยเป็นต้นไม้ย่อย ลักษณะของต้นไม้นะคะ เดี๋ยวเราจบที่ลักษณะของต้นไม้ ลักษณะของต้นไม้ที่เราจะพูดถึง ตัวแรก Binary Tree ไบ คือ 2 Binary Tree ก็คือต้นไม้ที่มีลูกได้ไม่เกิน 2 โหนดถูกไหมคะ ต้นไม้นี่ มีลูกได้ไหมเกิดน 2 เห็นไหม มีได้ไม่เกิน 2 มี 1 ก็ได้นะ มี 2 ก็ได้ ไม่มีก้ได้ แต่มี 3 ไม่ได้นะคะ มีลูก 3 ไม่เข้าข่ายตัวนี้นะ เป็นต้นไม้เฉย ๆ แต่ไม่ใช่ต้นไม้ Binary Tree อีก 1 ต้นไม้นะคะ BST ตรงนี้ BST ตัวนี้ หรือ Binary Search Tree มีลูก 2 เห็นไหมคะ มีลูก 2 หรือมีลูก 1 ก็ได้ แต่สิ่งที่เพิ่ม คือ ลูกด้านซ้าย ดูที่ 8 นะ ลูกด้านซ้าย ลูกด้านซ้าย น้อยกว่าพ่อ ลูกด้านขวามากกว่าพ่อ ซ้าย น้อยกว่าพ่อ ขวามากกว่าพ่อ ตัวนี้คือ Bi BST หรือว่า Binary Search Treeสังเกตง่าย ๆ เห็นไหมคะ ด้านขวาทุกตัว มากกว่า 8 เลย แต่ด้านซ้ายทุกตัวต้องน้อยกว่า 8 รูปนี้เหมือนกัน ด้านขวามากกว่า 50 ด้านซ้ายน้อยกว่า 50 นะคะ รูปนี้เหมือนกัน บนสุดคือ 7 ถูกหรือเปล่า ต้องน้อยกว่า 7 ด้านขวาต้องมากกว่า 7โอเค มี 3 แบบนะ มีต้นไม้ธรรมดา ทุกอย่างเป็นต้นไม้นะ มีต้นไม้ธรรมดา มี Binary Tree ลูก 2 แล้วก็ BST ลูก 2 เหมือนกันแต่ลูกด้านซ้ายน้อยกว่าพ่อ ลูกด้านขวามีค่ามากกว่าพ่อ โอเค เห็นไหม นะ เดี่ยวคราวหน้าเดี๋ยวครูจะมาทวนต้นไม้อีกครั้งหนึ่ง แล้วเราก็พูดถึงเรื่องต้นไม้ต่อ เราจะเพิ่มโหนดเข้าไปในต้นไม้ทำอย่างไร จะลบโหนดออกจากต้นไม้ทำอย่างไรนะคะโอเคนะคะ เดี๋ยวสัปดาห์หน้า เรามาเจอกันอีก วันนี้ก็น่าจะพอแค่สัปดาห์หน้า พอดีว่าครูติดลงพื้นที่ ครูอยากจะขยับเลื่อนเป็นพฤหัสบ่าย พฤหัสบดีเช้าก็ได้ค่ะสัปดาห์หน้านะคะ ครูเลื่อนเป็นพฤหัสบดีเช้านะ โอเค วันนี้เท่านี้ค่ะ