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

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

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

1. เริ่มจากการอ่านนิพจน์ทางคณิตศาสตร์ (Expression) ทีละตัว

2. ถ้าตัวที่ได้เป็น Operand (ตัวถูกดำเนินการ) ให้สร้างโหนดของ tree หนึ่งโหนดแล้ว push ข้อมูลลงบน Stack

3. หากตัวที่อ่านได้เป็น 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

ต้นไม้ทวิภาค