CoE KKU

Binary tree คือทรีที่แต่ละโนดมีโนดลูกได้ไม่เกิน 2 โนด รูปที่ 4.11 แสดงรูปแบบของไบนารีทรีซึ่งประกอบด้วยรากหนึ่งโนดและทรีย่อย 2 ทรีย่อย $T_L$ และ $T_R$ ซึ่งอาจจะเป็นทรีว่างก็ได้

คุณสมบัติที่สำคัญอย่างหนึ่งของไบนารีทรี คือ depth โดยเฉลี่ยของมันจะมีค่าน้อยกว่า N มาก จากการวิเคราะห์พบว่าความลึกเฉลี่ยของมันจะเป็น $O(\sqrt N)$ และสำหรับไบนารีชนิด Binary search tree จะมีค่าความลึกเฉลี่ยเป็น $O(log\ ⁡N)$ อย่างไรก็ตามความลึกของมันอาจมีค่าได้ถึง $N –1$ ดังรูปที่ 4.12

เนื่องจาก binary tree มีโนดลูกได้สูงสุดเพียง 2 โนด ดังนั้นเราจึงสามารถใช้การเชื่อมต่อโดยตรงได้ โครงสร้างของโนดประกอบด้วย key information และ pointers 2 ตัว (left และ right) ที่ชี้ไปยังโนดลูก (ดูรูปที่ 4.13)

class BinaryNode 
{  	Object 	element;
	BinaryNode	left;
	BinaryNode	right;
};

รูปที่ 4.13 คลาสของโนดในไปนารีทรี

เราสามารถเขียนรูปเพื่อแสดงไบนารีทรีได้ด้วยการใช้กล่องสี่เหลี่ยมแทนโนดเช่นเดียวกับที่ใช้ในลิงค์ลิสต์ แต่โดยทั่วไปแล้วเราจะแสดงรูปของทรีด้วยการใช้รูปวงกลมที่มีเส้นเชื่อมต่อกันและจะไม่แสดงเส้นเชื่อมต่อที่เป็น null เนื่องจากทรีที่มี N โนดอาจจะมี เส้นเชื่อมต่อ null ได้ถึง N+1 เส้น

รูปที่ 4.14 แสดงตัวอย่างของ expression tree โดยที่ leaves ของ expression tree เป็น operands เช่นค่าคงที่หรือตัวแปรและมีโนดอื่น ๆ เป็น operators ทรีแสดงนี้บังเอิญเป็นไบนารีทรีก็เนื่องจาก operators ทั้งหมดในทรีนั้นเป็น binary operators นั่นเอง

อย่างไรก็ตามอาจเป็นไปได้ที่โนดอาจจะมีโนดลูกมากกว่าสองโนดและก็อาจจะมีโนดลูกเพียงโนดเดียวได้เช่นกันเช่นกรณีที่เป็นเครื่องหมายลบที่เป็น unary minus เราสามารถหาค่าของ expression tree T โดยการใช้ operator ที่รากของทรีกระทำค่าที่ได้จากการหาค่าจากทรีย่อยซ้ายและขวาในแบบ recursive จากตัวอย่างค่าทางทรีย่อยซ้ายคือ a + (b * c) และค่าทางทรีย่อยขวา คือ ((d * e) + f ) * g ดังนั้นทรีทั้งหมด คือ (a + (b * c)) + (((d * e) + f ) * g)

เราสามารถเขียนนิพจน์แบบ infix expression ที่มีวงเล็บกำกับได้ด้วยการเขียนนิพจน์ด้านซ้ายที่มีวงเล็บกำกับในแบบ recursive และตามด้วยเครื่องหมายที่โนดรากและตามด้วยการเขียนนิพจน์ด้านขวาที่มีวงเล็บกำกับในแบบ recursive วิธีการดังกล่าวนี้ (left, node, right) เรียกว่า inorder traversal

วิธีการ traverse อีกวิธีหนึ่งคือการเข้าถึง (เพื่อพิมพ์ค่า) ทรีย่อยซ้าย, ทรีย่อยขวาแล้วตามด้วยตัว operator ในแบบ recursive และถ้าใช้วิธีการนี้กับทรีตัวอย่างก็จะได้ output เป็น a b c * + d e * f + g * + ซึ่งก็คือรูปแบบ postfix expression วิธีการ traverse ที่กล่าวนี้เรียกว่า postorder traversal ดังที่กล่าวมาแล้วในหัวข้อ 4.1

วิธีการ traverse วิธีที่สามคือการเข้าถึง (เพื่อพิมพ์ค่า) ตัว operator ก่อนเป็นลำดับแรกจากนั้นก็จะตามด้วยทรีย่อยซ้ายและทรีย่อยขวาในแบบ recursive จะได้นิพจน์ output เป็น + + a * b c * + * d e f g ซึ่งก็คือรูปแบบ prefix expression วิธีการ traverse ที่กล่าวนี้เรียกว่า postorder traversal

การสร้าง Expression Tree

ในหัวข้อนี้จะกล่าวถึงอัลกอริทึมที่ใช้ในการเปลี่ยนจาก postfix expression ไปเป็น expression tree ในหัวข้อก่อนหน้านี้เราได้กล่าวถึงอัลกอริทึมในการเปลี่ยนจาก infix ไปเป็น postfix มาแล้ว ดังนั้นเราจึงสามารถสร้าง expression tree จากอินพุตได้ทั้งสองแบบ

อัลกอริทึมที่ใช้คือ อ่านสัญลักษณ์จากนิพจน์อินพุตที่ละตัว

• ถ้าตัวที่อ่านมาเป็น operand ให้ทำการสร้างโนดของทรีขึ้นมาหนึ่งโนดแล้ว push มันลงบน stack
• ถ้าตัวสัญลักษณ์ที่อ่านมาเป็นตัว operator
  • ให้ทำการ pop จาก stack 2 ครั้ง ซึ่งจะได้ trees T1 และ T2 (T1 นำออกก่อน)
  • แล้วให้นำมาสร้างเป็นทรีใหม่ที่มีราก (root) เป็นตัว operator ที่อ่านมานั้นและมี left และ right children เป็น T2 และ T1 ตามลำดับ
  • จากนั้นให้ push ทรีใหม่ที่ได้นี้กลับลง stack เช่นถ้าอินพุต คือ a b + c d e + * *

สัญลักษณ์ที่อ่านสองตัวแรกเป็น operands เราจะสร้างทรีที่มีหนึ่งโนดสำหรับแต่ละสัญลักษณ์ที่อ่านแล้ว push ลง stack โดยจะกำหนดให้ stack มีสมาชิกเพิ่มจากซ้ายไปขวาเพื่อความสะดวกในการแสดง ดังนี้

ต่อไปอ่านเครื่องหมาย + ดังนั้นจะต้อง pop ทรีสองทรีจาก stack เพื่อสร้างทรีใหม่ จากนั้น push ลงบน stack ดังรูป

จากนั้นอ่าน c, d และ e และสร้างโนดของทรีสำหรับแต่ละสัญลักษณ์ที่อ่านแต่ละตัวและ push ลง stack

ต่อไปอ่านเครื่องหมาย + จะต้อง pop ทรีสองทรีจาก stack เพื่อสร้างทรีใหม่ จากนั้น push ลงบน stack ดังรูป

ต่อไปอ่านเครื่องหมาย * และ pop ทรีสองทรีจาก stack เพื่อสร้างทรีใหม่ที่มี * เป็นรากจากนั้น push ลงบน stack ดังรูป

อ่านสัญลักษณ์ตัวสุดท้ายและทำการรวมทรีสองทรีใน stack จะได้ทรีสุดท้ายดังนี้