Python - Tree Traversal อัลกอริทึม

Traversal เป็นกระบวนการในการเยี่ยมชมโหนดทั้งหมดของต้นไม้และอาจพิมพ์ค่าของมันด้วย เนื่องจากโหนดทั้งหมดเชื่อมต่อผ่านขอบ (ลิงค์) เรามักจะเริ่มต้นจากโหนดรูท (หัว) นั่นคือเราไม่สามารถสุ่มเข้าถึงโหนดในทรีได้ มีสามวิธีที่เราใช้ในการสำรวจต้นไม้ -

  • In-order Traversal
  • พรีออเดอร์ Traversal
  • Post-order Traversal

In-order Traversal

ในวิธีการข้ามผ่านนี้ทรีย่อยด้านซ้ายจะถูกเยี่ยมชมก่อนจากนั้นจึงไปที่รูทและตามมาในแผนผังย่อยด้านขวา เราควรจำไว้เสมอว่าทุกโหนดอาจเป็นตัวแทนของทรีย่อยเอง

ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดตรรกะการข้ามผ่าน Inorder จะถูกนำไปใช้โดยการสร้างรายการว่างและเพิ่มโหนดทางซ้ายก่อนตามด้วยรูทหรือโหนดหลัก ในที่สุดโหนดด้านซ้ายจะถูกเพิ่มเพื่อให้การข้ามผ่าน Inorder เสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Inorder traversal
# Left -> Root -> Right
    def inorderTraversal(self, root):
        res = []
        if root:
            res = self.inorderTraversal(root.left)
            res.append(root.data)
            res = res + self.inorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.inorderTraversal(root))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

[10, 14, 19, 27, 31, 35, 42]

พรีออเดอร์ Traversal

ในวิธีการข้ามผ่านนี้โหนดรูทจะถูกเยี่ยมชมก่อนจากนั้นทรีย่อยด้านซ้ายและสุดท้ายคือทรีย่อยด้านขวา

ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดตรรกะการส่งผ่านคำสั่งซื้อล่วงหน้าก็ถูกนำมาใช้โดยการสร้างรายการว่างและเพิ่มโหนดรูทก่อนตามด้วยโหนดด้านซ้าย ในที่สุดโหนดด้านขวาจะถูกเพิ่มเพื่อให้การส่งผ่านคำสั่งซื้อล่วงหน้าเสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Preorder traversal
# Root -> Left ->Right
    def PreorderTraversal(self, root):
        res = []
        if root:
            res.append(root.data)
            res = res + self.PreorderTraversal(root.left)
            res = res + self.PreorderTraversal(root.right)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PreorderTraversal(root))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

[27, 14, 10, 19, 35, 31, 42]

Post-order Traversal

ในวิธีการข้ามผ่านนี้โหนดรูทจะถูกเยี่ยมชมเป็นครั้งสุดท้ายดังนั้นชื่อ อันดับแรกเราสำรวจทรีย่อยด้านซ้ายจากนั้นทรีย่อยด้านขวาและสุดท้ายโหนดรูท

ในโปรแกรม python ด้านล่างเราใช้คลาส Node เพื่อสร้างตัวยึดตำแหน่งสำหรับโหนดรูทรวมทั้งโหนดซ้ายและขวา จากนั้นเราสร้างฟังก์ชันแทรกเพื่อเพิ่มข้อมูลให้กับต้นไม้ ในที่สุดลอจิกการข้ามผ่านหลังคำสั่งจะถูกนำมาใช้โดยการสร้างรายการว่างและเพิ่มโหนดด้านซ้ายก่อนตามด้วยโหนดด้านขวา ในที่สุดรูทหรือโหนดพาเรนต์จะถูกเพิ่มเพื่อให้การส่งผ่านหลังคำสั่งซื้อเสร็จสมบูรณ์ โปรดทราบว่ากระบวนการนี้ซ้ำสำหรับแต่ละแผนผังย่อยจนกว่าโหนดทั้งหมดจะถูกข้ามผ่าน

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data
# Insert Node
    def insert(self, data):

        if self.data:
            if data < self.data:
                if self.left is None:
                    self.left = Node(data)
                else:
                    self.left.insert(data)
            elif data > self.data:
                if self.right is None:
                    self.right = Node(data)
                else:
                    self.right.insert(data)
        else:
            self.data = data

# Print the Tree
    def PrintTree(self):
        if self.left:
            self.left.PrintTree()
        print( self.data),
        if self.right:
            self.right.PrintTree()

# Postorder traversal
# Left ->Right -> Root
    def PostorderTraversal(self, root):
        res = []
        if root:
            res = self.PostorderTraversal(root.left)
            res = res + self.PostorderTraversal(root.right)
            res.append(root.data)
        return res

root = Node(27)
root.insert(14)
root.insert(35)
root.insert(10)
root.insert(19)
root.insert(31)
root.insert(42)
print(root.PostorderTraversal(root))

เมื่อดำเนินการโค้ดด้านบนจะให้ผลลัพธ์ดังนี้ -

[10, 19, 14, 31, 42, 35, 27]