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

จากวิกิพีเดีย สารานุกรมเสรี
ไปยังการนำทาง ไปยังการค้นหา

ต้นไม้พิจน์ หรือ 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[แก้]

เป็นตัวอย่างต้นไม้นิพจน์ของ (a+(b*c)) + ((d+e)*f)

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