ต้นไม้ไบนารีที่สมดุลใน Python

ในไบนารีทรี แต่ละโหนดมีลูกสองคน นั่นคือลูกด้านซ้ายและลูกด้านขวา สมมติว่าเรามีไบนารีทรีและเราต้องตรวจสอบว่าต้นไม้นั้นสมดุลหรือไม่ ต้นไม้ไบนารีกล่าวกันว่ามีความสมดุลหากความแตกต่างของความสูงของต้นไม้ย่อยด้านซ้ายและต้นไม้ย่อยด้านขวามีค่าน้อยกว่าหรือเท่ากับ '1'

ตัวอย่าง

อินพุต-1:

ผลลัพธ์:

True

คำอธิบาย:

ต้นไม้ไบนารีที่กำหนดคือ [1,2,3, NULL, NULL, 6, 7] ความแตกต่างของความสูงของทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวาจะเท่ากับ '1' ดังนั้นจึงเป็นต้นไม้ที่มีความสูงสมดุล

อินพุต-2:

ผลลัพธ์:

False

คำอธิบาย:

ต้นไม้ไบนารีที่กำหนดคือ [1,2,3,4, NULL, NULL,NULL,5] ความแตกต่างของความสูงของทรีย่อยด้านซ้ายและทรีย่อยด้านขวามีค่ามากกว่า '1' ดังนั้นจึงไม่ใช่ต้นไม้ที่มีความสูงสมดุล

แนวทางในการแก้ปัญหานี้

วิธีการแบบเรียกซ้ำในการแก้ปัญหานี้คือการค้นหาความสูงของทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวา จากนั้นตรวจสอบว่า (height(leftsubstree) - height(rightsubtree) <=1) และคืนค่า True หรือ False ตามนั้น จากนั้น เราจะตรวจสอบแบบเรียกซ้ำสำหรับแต่ละโหนดของไบนารีทรี

• รับอินพุตของโหนดของไบนารีทรี
• กำหนดฟังก์ชันเพื่อค้นหาความสูงของต้นไม้
• ฟังก์ชันบูลีนสำหรับตรวจสอบแบบเรียกซ้ำว่าส่วนสูงของทรีย่อยด้านซ้ายและทรีย่อยด้านขวาต่างกันไม่เกิน '1' หรือไม่ ให้คืนค่า True
• ส่งคืนผลลัพธ์

ตัวอย่าง

class treenode:
   def __init__(self, data):
      self.data = data
      self.left = self.right = None
# funtion to find the height of the left subtree and right subtree
class height:
   def __init__(self):
      self.height = 0
# function to check if the tree is balanced or not
def isBalanced(root):
   lh = height()
   rh = height()
   if root is None:
      return True
   return (
      (abs(lh.height - rh.height) <= 1)
      and isBalanced(root.left)
      and isBalanced(root.right)
   )
root = treenode(1)
root.left = treenode(2)
root.right = treenode(3)
root.left.left = None
root.left.right = None
root.right.left = treenode(6)
root.right.right = treenode(7)
if isBalanced(root):
   print("Balanced")
else:
   print("Not Balanced")

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

ผลลัพธ์

Balanced

ต้นไม้ไบนารีที่กำหนด [1, 2, 3, NULL, NULL, 6, 7] ความแตกต่างของความสูงของทรีย่อยด้านซ้ายและแผนผังย่อยด้านขวาจะเท่ากับ '1' ดังนั้นจึงเป็นต้นไม้ที่มีความสูงสมดุล