ต้นไม้ทวิภาค (อังกฤษ : binary tree ) ในศาสตร์คอมพิวเตอร์ เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละปมมีปมลูกได้ไม่เกิน 2 ปม โดยแยกออกเป็นปมด้านซ้าย และปมด้านขวา ปมที่มีปมลูก เรียกว่า ปมพ่อแม่ และปมลูกอาจมีรีเฟอร์เรนซ์ไปยังปมพ่อแม่ของมัน ในโครงสร้างแบบต้นไม้จะมีปม ๆ หนึ่งเป็นปมบรรพบุรุษของทุกปม เราเรียกปมนี้ว่าปมราก การเข้าถึงปมทุกปมในโครงสร้างแบบต้นไม้ทำได้โดยเริ่มต้นจากปมราก และใช้รีเฟอร์เรนซ์ของปมนั้นท่องไปตามปมลูกด้านซ้ายและด้านขวาของมัน ต้นไม้ที่มีเฉพาะปมราก เรียกว่าต้นไม้ว่าง (null tree) ในต้นไม้ทวิภาค กิ่งหรือดีกรีของทุก ๆ ปมมีค่ามากที่สุดได้ไม่เกิน 2 ต้นไม้ที่มีปมจำนวน 'n' ปมจะมีกิ่งได้ไม่เกิน 'n-1' กิ่ง ต้นไม้ทวิภาคมักใช้สำหรับต้นไม้ค้นหาทวิภาค (binary search trees) และฮีพทวิภาค (binary heaps)
ต้นไม้แบบทวิภาค มีขนาด 9 และความสูง 3 โดยมีโหนดรากทีมีค่าเท่ากับ 2 ส่วนบนของต้นไม้ไม่สมดุลและไม่เรียงลำดับ
คำจำกัดความสำหรับต้นไม้ราก ขอบโดยตรง (A directed edge) หมายถึงเส้นที่เชื่อมจากปมพ่อแม่ไปยังปมลูก ปมรากเป็นปมที่ไม่มีปมพ่อแม่ ต้นไม้หนึ่งต้นมีปมรากเพียงปมเดียว ปมใบ (leaf node) เป็นปมที่ไม่มีปมลูก ความลึกของปม (The depth of a node) n เป็นความยาวของเส้นทางจากปมราก ไปจนถึงปมนั้น เซตของทุกปม ณ ความลึกที่ให้ บางครั้งเรียกวาสระดับของต้นไม้ ปมรากมีความลึกเท่ากับ 0 ความลึก หรือความสูง (The depth or height) ของต้นไม้ เป็นความยาวของเส้นทางจากปมรากไปจนถึงปมที่อยู่ลึกที่สุดของต้นไม้นั้น ปมพี่น้อง (Siblings nodes) เป็นปมที่มีปมพ่อแม่เดียวกัน ปม p เป็นปมบรรพบุรุษของปม q ถ้ามีเส้นทางจากปมรากไปถึงปม q และเรียกปม q ว่าเป็นปมลูกหลานของปม p ขนาดของปม (The size of a node) คือ จำนวนปมลูกหลานของมันทั้งหมดรวมทั้งตัวมันด้วย กิ่งเข้า (In-degree) ของปม คือจำนวนกิ่งที่เข้าหามัน กิ่งออก (Out-degree) ของปม คื่อจำนวนกิ่งที่ออกจากปมนั้น ปมรากเป็นเพียงปมเดียวในต้นไม้ที่มีกิ่งเข้า (In-degree) เท่ากับ 0 ปมในมีกิ่งออก เท่ากับ 0
ชนิดของต้นไม้ทวิภาค ต้นไม้ทวิภาคที่มีราก (A rooted binary tree) เป็นต้นไม้ซึ่งปมรากหนึ่งปม และทุกปมในต้นไม้มีปมลูกได้ไม่เกิน 2 ปม ต้นไม้ทวิภาคแบบเต็ม (A full binary tree) เป็นต้นไม้ซึ่งทุก ๆ ปมยกเว้นปมใบ มีปมลูก 2 ปม ต้นไม้ทวิภาคแบบสมบูรณ์ (A perfect binary tree) เป็นต้นไม้ทวิภาคแบบเต็ม ซึ่งปมใบทุกปมจะอยู่ในระดับเดียวกันหรือมีความลึกเท่ากัน complete binary tree เป็นต้นไม้ทวิภาคซึ่งปมทุกระดับยกเว้นระดับล่างสุด จะมีปมลูก 2 ปม และทุกปมจะเริ่มจากทางซ้ายสุด ต้นไม้ทวิภาคสมดุล เป็นต้นไม้ทวิภาค ซึ่งความลึกของต้นไม้ย่อย (subtree) สองต้นของทุก ๆ ปม เท่ากัน ปมใบของต้นไม้ย่อยจะมีระดับเท่ากัน
คุณสมบัติของต้นไม้ทวิภาค
นไม, แบบทว, ภาค, นไม, ทว, ภาค, งกฤษ, binary, tree, ในศาสตร, คอมพ, วเตอร, เป, นโครงสร, างข, อม, ลแบบต, นไม, งแต, ละปมม, ปมล, กได, ไม, เก, ปม, โดยแยกออกเป, นปมด, านซ, าย, และปมด, านขวา, ปมท, ปมล, เร, ยกว, ปมพ, อแม, และปมล, กอาจม, เฟอร, เรนซ, ไปย, งปมพ, อแม, ของม. tnimthwiphakh xngkvs binary tree insastrkhxmphiwetxr epnokhrngsrangkhxmulaebbtnimsungaetlapmmipmlukidimekin 2 pm odyaeykxxkepnpmdansay aelapmdankhwa pmthimipmluk eriykwa pmphxaem aelapmlukxacmiriefxrernsipyngpmphxaemkhxngmn inokhrngsrangaebbtnimcamipm hnungepnpmbrrphburuskhxngthukpm eraeriykpmniwapmrak karekhathungpmthukpminokhrngsrangaebbtnimthaidodyerimtncakpmrak aelaichriefxrernskhxngpmnnthxngiptampmlukdansayaeladankhwakhxngmn tnimthimiechphaapmrak eriykwatnimwang null tree intnimthwiphakh kinghruxdikrikhxngthuk pmmikhamakthisudidimekin 2 tnimthimipmcanwn n pmcamikingidimekin n 1 king tnimthwiphakhmkichsahrbtnimkhnhathwiphakh binary search trees aelahiphthwiphakh binary heaps tnimaebbthwiphakh mikhnad 9 aelakhwamsung 3 odymiohndrakthimikhaethakb 2 swnbnkhxngtnimimsmdulaelaimeriyngladbkhacakdkhwamsahrbtnimrak aekikhkhxbodytrng A directed edge hmaythungesnthiechuxmcakpmphxaemipyngpmluk pmrakepnpmthiimmipmphxaem tnimhnungtnmipmrakephiyngpmediyw pmib leaf node epnpmthiimmipmluk khwamlukkhxngpm The depth of a node n epnkhwamyawkhxngesnthangcakpmrak ipcnthungpmnn estkhxngthukpm n khwamlukthiih bangkhrngeriykwasradbkhxngtnim pmrakmikhwamlukethakb 0 khwamluk hruxkhwamsung The depth or height khxngtnim epnkhwamyawkhxngesnthangcakpmrakipcnthungpmthixyulukthisudkhxngtnimnn pmphinxng Siblings nodes epnpmthimipmphxaemediywkn pm p epnpmbrrphburuskhxngpm q thamiesnthangcakpmrakipthungpm q aelaeriykpm q waepnpmlukhlankhxngpm p khnadkhxngpm The size of a node khux canwnpmlukhlankhxngmnthnghmdrwmthngtwmndwy kingekha In degree khxngpm khuxcanwnkingthiekhahamn kingxxk Out degree khxngpm khuxcanwnkingthixxkcakpmnn pmrakepnephiyngpmediywintnimthimikingekha In degree ethakb 0 pminmikingxxk ethakb 0chnidkhxngtnimthwiphakh aekikhtnimthwiphakhthimirak A rooted binary tree epntnimsungpmrakhnungpm aelathukpmintnimmipmlukidimekin 2 pm tnimthwiphakhaebbetm A full binary tree epntnimsungthuk pmykewnpmib mipmluk 2 pm tnimthwiphakhaebbsmburn A perfect binary tree epntnimthwiphakhaebbetm sungpmibthukpmcaxyuinradbediywknhruxmikhwamlukethakn complete binary tree epntnimthwiphakhsungpmthukradbykewnradblangsud camipmluk 2 pm aelathukpmcaerimcakthangsaysud tnimthwiphakhsmdul epntnimthwiphakh sungkhwamlukkhxngtnimyxy subtree sxngtnkhxngthuk pm ethakn pmibkhxngtnimyxycamiradbethaknkhunsmbtikhxngtnimthwiphakh aekikhekhathungcak https th wikipedia org w index php title tnimaebbthwiphakh amp oldid 8868647, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ , อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
