Cây nhị phân cân bằng trong Python

Trong cây nhị phân, mỗi nút chứa hai nút con, tức là nút con bên trái và nút con bên phải. Giả sử chúng ta có một cây nhị phân và chúng ta cần kiểm tra xem cây đó có cân bằng hay không. Cây nhị phân được cho là cân bằng nếu sự khác biệt về chiều cao của cây con bên trái và cây con bên phải nhỏ hơn hoặc bằng '1'.

Ví dụ

Đầu vào-1:

Đầu ra:

True

Giải thích:

Cây nhị phân đã cho là [1,2,3, NULL, NULL, 6, 7]. Chênh lệch chiều cao của cây con bên trái và cây con bên phải của nó bằng '1', do đó nó là cây Cân bằng chiều cao.

Đầu vào-2:

Đầu ra:

False

Giải thích:

Cây nhị phân đã cho là [1,2,3,4, NULL, NULL, NULL, 5]. Chênh lệch chiều cao của cây con bên trái và cây con bên phải lớn hơn '1', do đó nó không phải là cây cân bằng chiều cao.

Phương pháp tiếp cận để giải quyết vấn đề này

Phương pháp đệ quy để giải quyết vấn đề này là tìm chiều cao của cây con bên trái và cây con bên phải, sau đó kiểm tra xem (height (leftsubstree) - height (rightsubtree) <=1) và trả về True hoặc False tương ứng. Sau đó, chúng tôi sẽ kiểm tra đệ quy từng nút của cây nhị phân.

• Nhận đầu vào của các nút của Cây nhị phân.
• Xác định một hàm để tìm chiều cao của cây.
• Một hàm Boolean để kiểm tra đệ quy nếu chênh lệch độ cao của cây con bên trái và cây con bên phải không quá '1', thì trả về True.
• Trả lại kết quả.

Ví dụ

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")

Chạy đoạn mã trên sẽ tạo ra kết quả là,

Đầu ra

Balanced

Cây nhị phân đã cho [1, 2, 3, NULL, NULL, 6, 7]. Chênh lệch chiều cao của cây con bên trái và cây con bên phải của nó bằng '1', do đó nó là cây Cân bằng chiều cao.