(อาจารย์สุธาสินี) คราวนี้นะคะ ก่อนที่เราจะขึ้นเรื่องใหม่ เดี๋ยวครูจะทวนของนะคะ ที่เราเรียนผ่านกันมาจะมี 2 เรื่องนะคะ ก็คือ Stack กับ Qeue Stack กับ Qeue นะคะ จะมีลักษณะจัดเก็บข้อมูลคล้าย ๆ กันถ้าเราเข้าใจ 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 มันจะถูกเอาออกมาทำงานก่อน แล้วตัวกำกับหรือตัวชี้ว่าข้อมูลล่าสุดที่อยู่ใน Stack มันอยู่ตรงไหน ใช่ไหมคะ Stack มันมีทางเข้าทางออกเพียงแค่ 1 ทางเท่านั้นเพราะฉะนั้น มันจะมีม Top นะคะ ตัว Top นี่เป็นตัวบอกว่าข้อมูลล่าสุดที่อยู่ใน Stack มันอยู่ใน Inde ที่เท่าไร เพราะฉะนั้น Top จะเป็นตัวบอกตำแหน่งว่าข้อมูลล่าสุดที่อยู่ในตำแหน่งนี่มันอยู่ตำแหน่งที่ Index ที่เท่าไหร่ ถ้าดราวาดเป็นตาราง 1 แถว หลายคอลใช่ไหมคะ Index ก็คือช่องแรกเราจะหมายเลขช่อ คือ 0 1 2 3 ไล่ไปเรื่อย ๆ เพราะฉะนั้น หมายเลข Index นั่นล่ะ คือตัว Top ที่บอกว่าตัวล่าสุดมันอยู่ช่องไหนนะคะ ถ้า stack ว่าง หมายถึงอะไร เราไม่มีข้อมูลอยู่ใน Stack เลย เพราะฉะนั้น ค่า Top จะเป็นเท่ากับ -1 คือไม่ได้บอกเลยว่าอยู่ช่องที่เท่าไรเลยนะคะ เพราะช่องเราเริ่มต้นที่ 0 นะ แต่จะเริ่มต้นที่ 0 นะคะ -1 นะคะ แล้วมาดูอีก 1 ตัว คือ qeue แล้วอันนี้จะใกล้ตัวเรามากขึ้น เหมือนกับที่เราไปต่อคิวซื้อข้าว ไปต่อคิวทำกิจกรรมต่าง ๆ ต่าง ๆ qeue เข้าก่อน ก็ต้องออกก่อน เพราะฉะนั้น qeue จะมีทางเข้าออกอยู่ 2 ทางนะคะ ออกข้างหน้า เข้าข้างหลังนะคะ คิว มีทางเข้าทางออก 2 ทาง เข้าข้างหลังออกข้างหน้าใช่ไหม คนมาก่อน ก็ต้องออกข้างหน้าเวลาเข้า ก็คือเข้าข้างหลังนะคะ เหมือนเราไปต่อคิวน่ะ มันมีทางเข้าทางออกกันคนละทาง คำส่งที่ใช้ในคิวมีอยู่ 2 ตัวเหมือนกัน เข้า กับเอาเข้ากับเอาออกเหมือนกันนะคะ เราจะใช้คำสั่ง Enqeue Enqeue Enter End End นะเข้าไป ส่วน Deque ก็คือเอาออก Deqeue ก็คือเอาข้อมูลออกมันก็จะตรงกับ Push กับ Pop คิวก็คือ Enqueue แล้วตัวกำกับข้อมูลที่อยู่ใน qeue เราใช้ค่าอะไรเป็นตัวกำกับ คิวเราก็มองเป็นลิสต์เหมือนกัน เป็นช่อง ๆ นะคะ เป็นหมายเลขช่อง เราเริ่มต้นหมายเลขช่องแรกก็คือ 0 ตัวกำกับจะมี 2 ตัวนะคะ ก็คือ front กับ rear front คือข้างหน้า rear คือข้างหลัง คือ F กับ R  Front จะเป็นตัวบอกข้อมูลว่าตัวไหนที่จะถูกเอาออก เพราะมันเอาออกข้างหน้านะคะ จะชี้อยู่ด้านหน้า เป็นตัวบอกว่า front กำกับอยู่ที่ช่องไหน ถ้าข้อมูลนั้นจะถูกเอาออก ส่วน rear จะเป็นตัวกำกับอยู่ที่ทางเข้านะคะ rear จะบอกตำแหน่งล่าสุดของข้อมูลว่าข้อมูลตัวที่เข้าล่าสุดใน queue อยู่ที่ตำแหน่งไหน ก็ระบุค่า index ก็คือหมายเลขช่องที่ค่าข้อมูลนั้นอยู่ คิวว่าง คิวว่าง แสดงว่ามันว่างนะ  คิวว่าง ก็คือไม่มีข้อมูลอยู่ใน 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 นะ โจทย์บอกตัวนี้คือ Stack นะคะ Stack คือเข้าข้างหลังออกข้างหลังใช่ไหมคะ Stack นะ เข้าข้างหลังออกข้างหลัง ก็คือทางเข้าทางออกอยู่ด้านหลังนะคะ คำสั่งตัวแรกดู ครูสั่งอะไรคะ Push Push คือใส่ ครู Puห อะไรคะ ครู Push เลข 3 คำสั่งคือใส่ ข้อมูลเลข 3 เพราะฉะนั้น ครุใส่ตรงไหน ใส่ข้างหลังเห็นไหมคะ ครูใส่เลข 3เห็นไหมคะ ครูใส่เลข 3 ลงมาลงมา มันมีที่ว่างตรงไหนคะ ครูหาทีว่างใส่นะนี่ครูเจอช่องนี้ว่างพอดีเลย เพราะฉะนั้น เลข 3 ครูก็อยู่ที่ช่องนี้นะคะ เลข 3 นี่ครูมาอยู่ที่ช่องสุดท้าย เพราะมันมีช่องใส่อยู่ช่องเดียวน่ะ ข้างหน้ามันเต็มหมดแล้วแล้วค่า Top จะเป็นอะไรค่า Top เป็นอะไร เราก็ต้องดูสิว่าค่าเลขช่องนี้มันอยู่ช่องหมายเลขอะไร เราก็ต้องเริ่มเขียนจากช่องก็คือ หมายเลขหมายเลข 3 หมายเลข 4 ถูกไหมคะ เพราะฉะนั้นแล้วนี่ ข้อมูลของครูอยู่ช่องหมายเลขอะไร หมายเลข 4 เพราะค่า Top จึงมีค่าเท่ากับ 4 เห็นไหมคะ มันตรงกันนะ ข้อมูลครูอยู่ตรงนี้ ครูมี คือ 4 Top ครูเลยมีค่าเท่ากับ 4 คำสั่ง Push นะคะ เดี๋ยวเรามาดูคำสั่ง Push อีก 1 ตัวดูสิคะ Push เหมือนกัน เห็นไหมคะ เจอ Push แสดงว่าใส่ข้อมูลใช่ไหม Push คือใส่ข้อมูล ใส่ข้างไหน คือใส่ข้างหลัง แล้วก็ใส่ลงมานะคะ คือ ใส่หมายเลข 10 พอครูใส่หมายเลข 10 เห็นไหม มันมีที่ว่างมันค่อย ๆ ไหลลงมา ไหลลงมานะคะ ก็เลยมาใส่ที่ช่องหลังเลข 3 แล้วหมายเลขช่องคืออะไร เราก็เขียนเหมือนเดิม 0 12 เพราะฉะนั้น ค่า 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 ได้ไหม ไม่ได้ถูกไหมคะ เพราะฉะนั้น 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 คือ Stack เอาข้อมูลอะไรเอาข้อมูล 5 ใส่ลงไปใน Stack 5 มาจากไหนนี่นะ มันบอกนี่คำสั่งมันบอกว่าเอาเลข 5 นะคะ ส่วน Pop คืออะไร คะเอาข้อมูลออกจาก Stack เอาข้อมูลข้างหลังหรือข้างหน้าออก Stack เอาข้อมูลข้างหลังหรือข้างหน้าออกข้างหลัง ถูกไหมคะ เอาข้อมูลข้างหลังออก เอาข้อมูลจากข้างหลังนะคะ ออก เดี๋ยวถ่ายรูปนะคะ ลงใน classroom หน่อยถ่ายรูปแบบฝึกหัดที่ทำนะคะ ลงใน Classroomเสร็จแล้วทุกคนถ่ายรูปนะคะ แล้วก็โพสต์ลงไปใน classroomถ่ายให้ครบ 3 แผ่นเลยนะ มี 4 คน ทุกหน้า เสร็จแล้วเดี๋ยวครูให้เบรก 5 นาทีนะ เดี๋ยวมาขึ้นเรื่องใหม่นะคะ จะให้เบรกก่อนจะได้เคลียร์ของเก่า โอเค มาต่อนะคะ มาต่อนะคะ จะเป็นอีก 1 โครงสร้างนะ เราพูดถึง Stack กับ Queueไปแล้วนะคะ Stack กับ queue มันข้อมูลมันจะเรียงกันเป็นแถวอาจจะเป็นแนวตั้งหรือแนวนอนก็ได้ แต่ทีนี้ ถ้ามีข้อมูลนะคะ ที่มันไม่ได้จัดเก็บเป็นแนวข้อมูลหรือเชิงโครงสร้าง เป็นแนวตั้งหรือแนวนอนนะคะ เป็นแนวตั้ง แนวนอน แต่ข้อมูลเรานะคะ มีลักษณะการจัดเก็บเป็นลำดับชั้น แล้วเราจะเก็บข้อมูลแบบไหน เราก้จะมีรูปแบบนะคะ แบบแรกเราจะเรียกว่า "โครงสร้างข้อมูลแบบต้นไม้" แล้วก็มีอีก 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, 9, 15 นะคะ พ่อของ 13 คืออะไร 23 โอเคคราวนี้ จากตรงนี้นะคะ เราดูการเรียกชื่อ หรือว่าลำดับของการเรียกชื่อโหลด 23 มันอยู่บนสุดเราจะเรียกว่ามันคือ รูตโหนดตัวนี้นะคะ โหนดที่อยู่บนสุดก็คือ root nodeตัวนี้นะคะ นะคะ เพราะว่ามันคือโหนดแรกสุดนะถัดมาโหนด 23 นี่เชื่อมไปยังโหนด 13 กับ 54 นะคะ มันเป็นพ่อของ 13 กับ 54 นะมันเป็นพ่อของ 13 กับ 5 4เสร็จแล้ว 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 มีลูกอยู่ 113 มีลูกอยู่ 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 คืออะไร 5 พี่น้อง หมายถึงพี่น้องพ่อเดียวกัน พี่น้องคือพี่น้องพ่อเดียวกัน พี่น้องของ 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 คน ชื่อ C B มีลูกอีก 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 เส้นนะคะ เพราะมีลูก 3 คน วาดลูกก่อน ลูกคนแรกชื่อ D, E แล้วก็ F ใช่ไหมคะ คนอื่นไม่มีลูกเลยนะ D กับ E ไม่มีลูกเลย แต่ F คนเดียวที่มีลูกใช่ไหมคะ ก็คือ Z อันนี้เครือญาติของบ้านสมชายใช่ไหมคะ เป็นแบบนี้ ครูถามต่อ จากรูปนี้ รูตโหนดคืออะไรคะ รูตโหนดคืออะไร ก็คือโหนดที่ชื่อสมชาย ถูกไหม ก็เขาอยู่บนสุด เขาเป็นต้นตระกูลของบ้านหลังนี้ ลิฟโหนดคืออะไรคะ ลีฟโหนด ลีฟโหนด คือ โหลดที่มีลูกไหม ไม่มีลูก เพราะฉะนั้น อันไหนที่ไม่มีลูก C, D, E แล้วก็ Z เห็นไหมคะ คนเหล่านี้เป็นโสด ถ้าเทียบนะ คนเหล่านี้เป็นโสดยังไม่ได้แต่งงานเลยนะคะ ยังเป็นโสดอยู่ไม่มีลูกพี่น้องของ D คือใครพี่น้องของ D มีใครบ้าง D. Dog D. Dog พี่น้องของ D. Dog มีใครบ้าง E กับ F ใช่ไหมคะ พี่น้องของ D. Dog C มีพี่น้องไหมคะ C มีพี่น้องไหม ไม่มี C ไม่มีพี่น้องนะคะ C เป็นลูกคนเดียวไม่มีพี่น้อง Z มีพี่น้องไหมไม่มีเป็นลูกคนเดียวเหมือนกัน Z ก็เป็นลูกคนเดียว โอเคจากเครือตรงนี้ใช่ไหมคะ เราวาดได้ต้นไม้ 1 ต้นนะ  ถัดมาต้นไม้นี่ ในต้นไม้นะคะ เราสามารถมีต้นไม้ย่อย ที่อยู่ภายในต้นไม้ได้ เช่น จากรูปนี้ ตรงนี้ ฝั่งซ้ายของ 23 ก็คือฝั่งนี้ถูกไหมคะ ต้นไม้ย่อยนะ ของ 23 ฝั่งขวาตรงนี้ก็คือต้นไม้ย่อยนะคะ เห็นไหม เพราะว่ามันมีกิ่งก้านสาขาแตกลงมาตรงนี้ก็เลยเป็นต้นไม้ย่อย ลักษณะของต้นไม้นะคะ เดี๋ยวเราจบที่ลักษณะของต้นไม้ ลักษณะของต้นไม้มีลักษณะอยู่ 2 แบบ ที่เราจะพูดถึง ตัวแรก Binary Tree Bi คืออะไรคะ ก็คือ 2 Binary Tree ก็คือต้นไม้ที่มีลูกได้ไม่เกิน 2 โหนดถูกไหมคะ ต้นไม้นี่ มีลูกได้ไหม เกิดน 2 เห็นไหม มีได้ไม่เกิน 2 มี 1 ก็ได้นะ มี 2 ก็ได้ ไม่มีก็ได้ แต่มี 3 ไม่ได้นะคะ มีลูก 3 ไม่เข้าข่ายตัวนี้นะ เป็นต้นไม้เฉย ๆ แต่ไม่ใช่ต้นไม้ Binary Tree อีก 1 ต้นไม้นะคะ BST ตรงนี้ BST ตัวนี้ หรือ BinarySearch Treeมีลูก 2 เห็นไหมคะ มีลูก 2 หรือมีลูก 1 ก็ได้แต่สิ่งที่เพิ่ม คือ ลูกด้านซ้ายดูที่ 8 นะ ลูกด้านซ้าย ลูกด้านซ้าย น้อยกว่าพ่อลูกด้านขวามากกว่าพ่อซ้าย น้อยกว่าพ่อ ขวามากกว่าพ่อ ตัวนี้คือ Bi BST หรือว่า Binary Search Tree โอเค สังเกตง่าย ๆ เห็นไหมคะ ด้านขวาทุกตัว มากกว่า 8 เลย แต่ด้านซ้ายทุกตัวต้องน้อยกว่า 8 รูปนี้เหมือนกัน ด้านขวามากกว่า 50 ด้านซ้ายน้อยกว่า 50 นะคะ รูปนี้เหมือนกัน บนสุดคือ 7 ถูกหรือเปล่า ด้านซ้ายต้องน้อยกว่า 7 ด้านขวาต้องมากกว่า 7 โอเค มี 3 แบบนะ มีต้นไม้ธรรมดา ทุกอย่างเป็นต้นไม้นะ มีต้นไม้ธรรมดามี Binary Tree ลูก 2แล้วก็ BST ลูก 2 เหมือนกันแต่ลูกด้านซ้ายน้อยกว่าพ่อ ลูกด้านขวามีค่ามากกว่าพ่อ โอเคเห็นไหม นะ เดี่ยวคราวหน้าเดี๋ยวครูจะมาทวนต้นไม้อีกครั้งหนึ่งแล้วเราก็พูดถึงเรื่องต้นไม้ต่อ เราจะเพิ่มโหนดเข้าไปในต้นไม้ทำอย่างไร จะลบโหนดออกจากต้นไม้ทำอย่างไรนะคะ  โอเคนะคะ เดี๋ยวสัปดาห์หน้าเรามาเจอกันอีก วันนี้ก็น่าจะพอแค่ เดี๋ยวครูเช็กชื่อ สัปดาห์หน้าครูติดลงพื้นที่ เลื่อนเป็นพฤหัสบดี บ่าย