Python - ต้นไม้ไบนารี

ต้นไม้แสดงถึงโหนดที่เชื่อมต่อกันด้วยขอบ เป็นโครงสร้างข้อมูลที่ไม่ใช่เชิงเส้น มีคุณสมบัติดังต่อไปนี้

• โหนดหนึ่งถูกทำเครื่องหมายเป็นโหนดรูท
• ทุกโหนดอื่นที่ไม่ใช่รูทเชื่อมโยงกับโหนดหลัก
• แต่ละโหนดสามารถมีจำนวนโหนด chid ได้

เราสร้างโครงสร้างข้อมูลแบบทรีใน python โดยใช้โหนดระบบปฏิบัติการแนวคิดที่กล่าวถึงก่อนหน้านี้ เรากำหนดโหนดหนึ่งโหนดเป็นโหนดรูทจากนั้นเพิ่มโหนดอื่น ๆ เป็นโหนดลูก ด้านล่างนี้คือโปรแกรมสำหรับสร้างโหนดรูท

สร้างรูท

เราเพียงแค่สร้างคลาส Node และเพิ่มกำหนดค่าให้กับโหนด สิ่งนี้จะกลายเป็นทรีที่มีโหนดรูทเท่านั้น

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data


    def PrintTree(self):
        print(self.data)

root = Node(10)

root.PrintTree()

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

10

แทรกเข้าไปในต้นไม้

ในการแทรกลงในต้นไม้เราใช้คลาสโหนดเดียวกันที่สร้างไว้ด้านบนและเพิ่มวิธีการแทรกเข้าไปวิธีการแทรกจะเปรียบเทียบค่าของโหนดกับโหนดแม่และตัดสินใจที่จะเพิ่มเป็นโหนดซ้ายหรือโหนดขวา ในที่สุดก็ใช้วิธี PrintTree ในการพิมพ์ต้นไม้

class Node:

    def __init__(self, data):

        self.left = None
        self.right = None
        self.data = data

    def insert(self, data):
# Compare the new value with the parent node
        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()

# Use the insert method to add nodes
root = Node(12)
root.insert(6)
root.insert(14)
root.insert(3)

root.PrintTree()

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

3 6 12 14

ข้ามต้นไม้

ต้นไม้สามารถข้ามผ่านได้โดยการตัดสินใจเลือกลำดับเพื่อเยี่ยมชมแต่ละโหนด อย่างที่เห็นได้ชัดว่าเราสามารถเริ่มต้นที่โหนดจากนั้นไปที่แผนผังย่อยด้านซ้ายก่อนและแผนผังย่อยด้านขวาถัดไป หรือเราสามารถไปที่แผนผังย่อยด้านขวาก่อนและด้านซ้ายย่อยถัดไป ดังนั้นจึงมีชื่อที่แตกต่างกันสำหรับวิธีการข้ามต้นไม้เหล่านี้ เราศึกษารายละเอียดเหล่านี้ในบทการใช้อัลกอริทึมการสำรวจต้นไม้ที่นี่ Tree Traversal Algorithms