วิธีคิดแบบนักวิทยาการคอมพิวเตอร์/Trees

บทที่ 20

Tree ถูกสร้างขึ้นด้วย nodes เหมือน linked list โดย tree ชนิดทั่วๆไป คือ binary tree ซึ่งมีลักษณะแบบ node หนึ่งเก็บค่าอ้างอิงถึง node อีก 2 ตัว (เป็น null ได้) การอ้างอิงคือการอ้างอิงที่ left และ right subtrees เหมือน list nodes ตัว tree nodes ก็จะมีการเก็บตัว cargo ลองดู state diagram สำหรับ tree

ไฟล์:Ch20-1.jpg

เพื่อหลีกเลี่ยงในการทำให้รูปมันดูเกะกะ เราจึงหลีกเลี่ยงการแสดง node ที่เป็น Nones

ส่วนบนสุดของ tree (หมายถึง node tree) จะเรียกว่า root เป็นการเปรียบเทียบกับต้นไม้ node อื่นๆจะเรียกว่า branches และ node ปลายสุดที่ไม่มีการอ้างอิงไปยัง node ใดแล้วจะเรียกว่า leaves มันดูแปลกที่เราวาดภาพที่ให้ root อยู่บนสุดและให้ leaves อยู่ล่างสุด แต่ว่ามันไม่ใช่สิ่งที่แปลก

เพื่อทำให้มันดูยากมากขึ้นนักวิทยาศาสตร์คอมพิวเตอร์ได้ผสมการเปรียบทียบกับ family tree เข้าไป ส่วน node บนสุดจะเรียกว่า parent และ node ที่มันอ้างอิงไปถึงจะเรียกว่า children ส่วน node ที่มี parent เหมือนกันเรียกว่า siblings

สุดท้ายคือศัพท์ทางเรขาคณิตที่มีการเรียกถึงตัว tree เราพูดถึงด้านซ้ายและด้านขวาไปแล้วแต่ในที่นี้จะเป็น up (parent/root) และ down (children/leaves) ดังนั้น nodes ทั้งหมดที่มีระยะห่างจาก root จะถูกประกอบกันเป็น level of the tree

เราน่าจะไม่ต้องการการเปรียบเทียบทั้ง 3 แบบนี้ แต่ต้องยอมรับว่ามันก็เป็นอย่างนั้น

เหมือน linked lists โครงสร้างข้อมูลของ tree เป็นแบบ recursive data มันถูกกำหนดให้เป็นแบบ recursively

Tree ประกอบด้วย

• Tree ที่ว่างเปล่าจะถูกแทนด้วย None

• Node จะเก็บค่า object และอ้างอิงไปยัง tree อีก 2 ตัว

20.1 Building trees

กระบวนการในการประกอบตัว tree เหมือนกับการประกอบ linked list โดยมี constructor แต่ละอันเรียกขึ้นมาเพื่อสร้าง node หนึ่ง node

class Tree:

def __init__(self, cargo, left=None, right=None):

self.cargo = cargo

self.left = left

self.right = right

def __str__(self):

return str(self.cargo)

Cargo สามารถเป็นชนิดข้อมูลใดก็ได้ แต่ left และ right จะต้องเป็น tree node โดย left และ right เป็นค่าแบบ optional ค่า default คือ None

เพื่อพิมพืค่า tree เราก้แค่พิมพ์ค่า cargo

ทางหนึ่งเพื่อสร้าง tree จากด้านล่างคือการสร้าง child node ขึ้นมาก่อน

left = Tree(2)

right = Tree(3)

จากนั้นจึงสร้าง parent node แล้ว link มันเข้ากับ child node

tree = Tree(1, left, right)

เราสามารถเขียน code ให้รัดกุมกว่านี้โดยการเรียก nesting constructor

>>> tree = Tree(1, Tree(2), Tree(3))

ทั้งสองทางผลลัพธ์ที่ได้จะเป็นการสร้าง tree แบบที่แสดงให้เห็นในตอนต้นของบทนี้

= 20.2 Traversing trees

เมื่อใดก็ตามที่เราสร้างโครงสร้างข้อมูลใหม่คำถามแรกคือเราจะเข้าไปเรียกข้อมูลในตัวมันได้อย่างไร การเข้าไปใน tree ซึ่งมีรูปแบบ recursively เป็นต้นว่าถ้า tree เก็บค่า integers ไว้ใน cargo ฟังก์ชันนี้จะ return ค่า sum ออกมา

def total(tree):

if tree == None: return 0

return total(tree.left) + total(tree.right) + tree.cargo

Base case คือ tree ที่ว่างเปล่าซึ่งไม่มี cargo ดังนั้นค่า sum จึงเป็น 0 ขั้นตอนในการทำงานแบบ recursive จะต้องมี 2 recursive เพื่อหา sum ของ child trees เมื่อมันทำงานเสร็จแล้วจึงมาบวกกับค่าใน cargo ของ parent และ return ผลรวมทั้งหมด

20.3 Expression trees

Tree สามารถแสดงค่าโครงสร้างของ expression ได้อย่างเป็นธรรมชาติไม่เหมือนสัญลักษณ์อื่น มันสามารถแสดงการคำนวณได้อย่างไม่คลุมเครือ เป็นต้นว่า infix expression 1 + 2 * 3 เป็นความคลุมเครือที่อย่างน้อยเราก็รู้ว่าจะต้องทำการคูณก่อนการบวก

Expression นี้แสดงการคำนวณในรูปแบบ tree

ไฟล์:Ch20-2.jpg

Node ของ tree สามารถเป็น operands หรือ operator ได้ operand คือ leaf nodes ส่วนของ operator node จะเก็บค่าอ้างอิงไปยัง operands (operator ทั้งหมดคือ binary หมายถึงมันจะมี operand 2 ตัวแน่นอน)

เราสามารถสร้าง tree ได้ดังนี้

>>> tree = Tree('+', Tree(1), Tree('*', Tree(2), Tree(3)))

ดูจากรูปภาพ ไม่มีคำถามสำหรับลำดับการ operations การคูณจะเกิดก่อน ตามด้วยการบวก

Expression tree ใช้ได้หลากหลาย ตัวอย่างในบทนี้จะแสดงการใช้ tree ในการแปลง expression ไปเป็น postfix, prefix และ infix เหมือนกับ tree ที่ใช้ใน compilers เพื่อ parse, optimize และ translate program