โปรแกรมที่จะลบโหนดทั้งหมดที่มีลูกเพียงคนเดียวจากต้นไม้ไบนารีใน Python?

สมมติว่าเรามีรากต้นไม้ไบนารี เราต้องลบโหนดทั้งหมดที่มีลูกเพียงคนเดียว

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์ที่ได้จะเป็น

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้:

• กำหนดวิธีการที่เรียกว่าแก้ปัญหา () ซึ่งจะเป็นการรูทต้นไม้

• ถ้ารูทเป็นโมฆะ

  • คืนค่ารูท

• ถ้าทางซ้ายของรูทเป็นโมฆะ และทางขวาของรูทเป็นโมฆะ

  • คืนค่ารูท

• หากรูทเหลือเป็นโมฆะ

  • ส่งคืนการแก้ (ทางขวาของรูท)

• หากสิทธิ์ของรูทเป็นโมฆะ

  • คืนค่าการแก้ (ด้านซ้ายของรูท)

• ทางซ้ายของรูท :=แก้ (ทางซ้ายของรูท)

• ทางขวาของรูท :=แก้ (ทางขวาของรูท)

• คืนค่ารูท

ตัวอย่าง

คลาส TreeNode:def __init__(ตัวเอง ข้อมูล ซ้าย =ไม่มี ขวา =ไม่มี):self.data =ข้อมูล self.left =ซ้าย self.right =rightdef print_tree(root):ถ้า root ไม่ใช่ None:print_tree( root.left) พิมพ์ (root.data, end =', ') คลาส print_tree (root.right) วิธีแก้ไข:def แก้ไข (ตัวเอง, รูท):ถ้าไม่ใช่รูท:ส่งคืนรูทหากไม่ใช่ root.left และไม่ใช่ root.right:คืนค่า root หากไม่ใช่ root.left:คืนค่า self.solve (root.right) หากไม่ใช่ root.right:คืนค่า self.solve (root.left) root.left =self.solve (root.left) root.right =self แก้ (root.right) ส่งคืน rootob =โซลูชัน ()root =TreeNode(1)root.left =TreeNode(2)root.right =TreeNode(3)root.left.left =TreeNode (4) root.right.right =TreeNode(5)root.left.left.right =TreeNode(6)root.right.right.left =TreeNode(7)root.right.right.right =TreeNode(8)res =ob.solve(ราก)print_tree( res)

อินพุต

ผลลัพธ์

6, 1, 7, 5, 8,