Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ต้นไม้ทวิภาค (อังกฤษ: binary tree) ในศาสตร์คอมพิวเตอร์ เป็นโครงสร้างข้อมูลแบบต้นไม้ซึ่งแต่ละปมมีปมลูกได้ไม่เกิน 2 ปม โดยแยกออกเป็นปมด้านซ้าย และปมด้านขวา ปมที่มีปมลูก เรียกว่า ปมพ่อแม่ และปมลูกอาจมีรีเฟอร์เรนซ์ไปยังปมพ่อแม่ของมัน ในโครงสร้างแบบต้นไม้จะมีปม ๆ หนึ่งเป็นปมบรรพบุรุษของทุกปม เราเรียกปมนี้ว่าปมราก การเข้าถึงปมทุกปมในโครงสร้างแบบต้นไม้ทำได้โดยเริ่มต้นจากปมราก และใช้รีเฟอร์เรนซ์ของปมนั้นท่องไปตามปมลูกด้านซ้ายและด้านขวาของมัน ต้นไม้ที่มีเฉพาะปมราก เรียกว่าต้นไม้ว่าง (null tree) ในต้นไม้ทวิภาค กิ่งหรือดีกรีของทุก ๆ ปมมีค่ามากที่สุดได้ไม่เกิน 2 ต้นไม้ที่มีปมจำนวน 'n' ปมจะมีกิ่งได้ไม่เกิน 'n-1' กิ่ง ต้นไม้ทวิภาคมักใช้สำหรับต้นไม้ค้นหาทวิภาค (binary search trees) และฮีพทวิภาค (binary heaps)
คำจำกัดความสำหรับต้นไม้ราก
- ขอบโดยตรง (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) สองต้นของทุก ๆ ปม เท่ากัน ปมใบของต้นไม้ย่อยจะมีระดับเท่ากัน
คุณสมบัติของต้นไม้ทวิภาค
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
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 swnbnkhxngtnimimsmdulaelaimeriyngladbkhacakdkhwamsahrbtnimrakkhxbodytrng A directed edge hmaythungesnthiechuxmcakpmphxaemipyngpmluk pmrakepnpmthiimmipmphxaem tnimhnungtnmipmrakephiyngpmediyw pmib leaf node epnpmthiimmipmluk khwamlukkhxngpm The depth of a node n epnkhwamyawkhxngesnthangcakpmrak ipcnthungpmnn estkhxngthukpm n khwamlukthiih bangkhrngeriykwaradbkhxngtnim 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 0chnidkhxngtnimthwiphakhtnimthwiphakhthimirak 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