แนวคิดพื้นฐาน
ต้นไม้ไบนารีถูกกำหนดให้เป็นต้นไม้ที่ไม่มีโหนดใดสามารถมีลูกมากกว่าสองคนได้ ระดับสูงสุดของโหนดใด ๆ คือสอง นี่แสดงว่าระดับของไบนารีทรีเป็นศูนย์หรือหนึ่งหรือสอง
ในรูปด้านบน ต้นไม้ไบนารีประกอบด้วยรูทและทรีย่อยสองทรี TreeLeft &TreeRight โหนดทั้งหมดทางด้านซ้ายของไบนารีทรีจะแสดงเป็นทรีย่อยด้านซ้าย และโหนดทั้งหมดทางด้านขวาของไบนารีทรีจะเรียกว่าทรีย่อยที่ถูกต้อง
การนำไปใช้
ต้นไม้ไบนารีมีลูกสูงสุดสองคน เราสามารถกำหนดพอยน์เตอร์ให้กับพวกเขาได้โดยตรง การประกาศโหนดทรีจะเหมือนกับโครงสร้างสำหรับรายการที่เชื่อมโยงแบบทวีคูณ โดยที่โหนดเป็นโครงสร้างที่มีข้อมูลสำคัญพร้อมพอยน์เตอร์สองตัว (ซ้ายและขวา) ไปยังโหนดอื่น
การประกาศโหนดไบนารีทรี
typedef struct tree_node *tree_ptr;
struct tree_node
{
element_type element1;
tree_ptr left1; tree_ptr right1;
};
typedef tree_ptr TREE; ประเภทของไบนารีทรี
ต้นไม้ไบนารีอย่างเคร่งครัด
ต้นไม้ไบนารีอย่างเคร่งครัดถูกกำหนดให้เป็นต้นไม้ไบนารีที่โหนดทั้งหมดจะมีลูกเป็นศูนย์หรือสองคน ไม่รวมชายด์หนึ่งคนในโหนดใด ๆ
ต้นไม้เอียง
ต้นไม้เอียงถูกกำหนดให้เป็นต้นไม้ไบนารีซึ่งทุกโหนดยกเว้นใบไม้มีโหนดย่อยเพียงโหนดเดียว ต้นไม้ไบนารีเบ้มีสองประเภท ได้แก่ ต้นไม้ไบนารีเบ้ซ้ายและต้นไม้ไบนารีเบ้ขวา
ไบนารีทรีเบ้ซ้าย
ต้นไม้เบ้ซ้ายมีโหนดที่เกี่ยวข้องกับลูกด้านซ้ายเท่านั้น เป็นไบนารีทรีที่มีเฉพาะทรีย่อยด้านซ้ายเท่านั้น
ไบนารีทรีเบ้ขวา
ต้นไม้เบ้ขวามีโหนดที่เกี่ยวข้องกับชายด์เท่านั้น เป็นไบนารีทรีที่มีเฉพาะทรีย่อยที่ถูกต้องเท่านั้น
ไบนารีทรีเต็มหรือทรีไบนารีที่เหมาะสม
ต้นไม้ไบนารีถูกกำหนดให้เป็นต้นไม้ไบนารีแบบเต็ม ถ้าใบทั้งหมดอยู่ในระดับเดียวกัน และโหนดที่ไม่ใช่ใบไม้ทุกโหนดมีลูกสองคนพอดี และควรประกอบด้วยจำนวนโหนดสูงสุดที่เป็นไปได้ในทุกระดับ ต้นไม้ไบนารีเต็มความสูง h มีโหนดสูงสุด 2h+1 – 1 โหนด
ต้นไม้ไบนารีที่สมบูรณ์
ทุกโหนดที่ไม่ใช่โหนดปลายสุดมีลูกสองคนพอดี แต่ทุกใบไม่จำเป็นต้องอยู่ในระดับเดียวกัน ต้นไม้ไบนารีที่สมบูรณ์ถูกกำหนดให้เป็นหนึ่งที่ทุกระดับมีจำนวนโหนดสูงสุดยกเว้นระดับสุดท้าย ควรเติมองค์ประกอบระดับสุดท้ายจากทิศทางซ้ายไปขวา
ไบนารีทรีเกือบสมบูรณ์
ต้นไม้ไบนารีที่เกือบจะสมบูรณ์ถูกกำหนดให้เป็นต้นไม้ซึ่งแต่ละโหนดที่มีลูกที่ถูกต้องมีลูกด้านซ้ายด้วย การมีลูกทางซ้ายไม่จำเป็นต้องมีโหนดเพื่อมีลูกที่ถูกต้อง
ความแตกต่างระหว่างต้นไม้ทั่วไปและต้นไม้ไบนารี
ต้นไม้ทั่วไป
- ต้นไม้ทั่วไปไม่จำกัดจำนวนลูก
- การประเมินนิพจน์เป็นเรื่องยากสำหรับต้นไม้ทั่วไป
ต้นไม้ไบนารี
- ไบนารีทรีมีลูกได้สูงสุดสองคน
- การประเมินนิพจน์นั้นง่ายในไบนารีทรี
การประยุกต์ใช้ต้นไม้
- การจัดการนิพจน์ทางคณิตศาสตร์
- การสร้างตารางสัญลักษณ์
- การวิเคราะห์ไวยากรณ์
- การเขียนไวยากรณ์
- การสร้างแผนผังนิพจน์
