ต้นไม้นิพจน์ทวิภาค

ต้นไม้พิจน์ทวิภาค () เป็นต้นไม้แบบไบนารี (Binary Tree) ที่มีการสร้างขึ้นจากตัวกระทำ (operand) และ เครื่องหมาย (operators) ทางคณิตศาสตร์ของนิพจน์ โดยการวางตัวกระทำที่ leaf node และวางเครื่องหมายไว้ที่ root node

 การสร้าง Expression Tree 
จะมีการนำ Postfix Expression มาใช้ในการทำ Expression tree 

เริ่มจากการอ่านนิพจน์ทางคณิตศาสตร์ (Expression) ทีละตัว
ถ้าตัวที่ได้เป็น Operand (ตัวถูกดำเนินการ) ให้สร้างโหนดของ tree หนึ่งโหนดแล้ว push ข้อมูลลงบน Stack
หากตัวที่อ่านได้เป็น Operator (ตัวดำเนินการ) ให้ทำการ pop ข้อมูลออกจาก Stack 2 ครั้ง เนื่องจาก Operator ใช้เป็น Binary Operator (Operator 1 ตัว ต้องการ Operand 2 ตัว) ซึ่งจะได้ trees T1 และ T2 (T1 นำออกก่อน) แล้วให้นำมาสร้างเป็น tree ใหม่ที่มีราก (root) เป็นตัว operator และมี left และ right children เป็น T2 และ T1 ตามลำดับ จากนั้นให้ใส่ tree ใหม่นี้กลับลง stack

 ตัวอย่างของ Expression Tree 

 Code ของ Expression Tree 
class ExpressionTree:
	def __init__(self , value):
		self.value = value
		self.left = None
		self.right = None

def isOperator(char):
	if (char == '+' or char == '-' or char == '*'
		or char == '/' or char == '^'):
		return True
	else:
		return False

def buildTree(postfix):
	stack = []

	for char in postfix :
		if not isOperator(char):
			t = ExpressionTree(char)
			stack.append(t)
		else:
			t = ExpressionTree(char)
			t1 = stack.pop()
			t2 = stack.pop()

			t.right = t1
			t.left = t2

			stack.append(t)
	t = stack.pop()
	return t


def inorder(t):
	alist = []
	if t is not None:
		alist.append(t.value)
		alist = inorder(t.left) + alist + inorder(t.right)
	return alist

 แหล่งอ้างอิง 
geeksforgeeks Expression Tree ค้นหาเมื่อ 30 มีนาคม 2561
nattee ต้นไม้นิพจน์ ค้นหาเมื่อ 30 มีนาคม 2561

หมวดหมู่:ต้นไม้ทวิภาค