Tìm cây con hoàn chỉnh lớn nhất trong cây nhị phân trong Python

Cho một cây nhị phân, ta cần tìm kích thước của cây con hoàn chỉnh (complete sub-tree) lớn nhất. Như ta biết, một cây nhị phân hoàn chỉnh là cây mà tất cả các cấp độ đều được lấp đầy hoàn toàn, trừ có thể cấp độ cuối cùng, và cấp độ cuối cùng có tất cả các khóa nằm sát bên trái nhất có thể.

Ví dụ, nếu đầu vào như hình dưới đây:

thì kết quả sẽ là kích thước 4 và duyệt inorder sẽ là 10, 45, 60, 70.

Thuật toán giải quyết

• Định nghĩa kiểu trả về với các tham số: isComplete, isPerfect (mặc định False), size (mặc định 0), rootTree (mặc định None).
• ret_type := returnType.
• Nếu root là null:
  • ret_type.isPerfect := True, ret_type.isComplete := True.
  • ret_type.size := 0, ret_type.rootTree := None.
  • Trả về ret_type.
• left_tree := checkCompleteness(root.left), right_tree := checkCompleteness(root.right).
• Nếu left_tree.isPerfect == True và right_tree.isComplete == True và chiều cao cây trái và phải bằng nhau:
  • ret_type.isComplete := True, ret_type.isPerfect := right_tree.isPerfect.
  • ret_type.size := left_tree.size + right_tree.size + 1.
  • ret_type.rootTree := root.
  • Trả về ret_type.
• Nếu left_tree.isComplete == True và right_tree.isPerfect == True và chiều cao cây trái = chiều cao cây phải + 1:
  • ret_type.isComplete := True, ret_type.isPerfect := False.
  • ret_type.size := left_tree.size + right_tree.size + 1.
  • ret_type.rootTree := root.
  • Trả về ret_type.
• Ngược lại:
  • ret_type.isPerfect := False, ret_type.isComplete := False.
  • ret_type.size := max(left_tree.size, right_tree.size).
  • Nếu left_tree.size > right_tree.size thì ret_type.rootTree := left_tree.rootTree, ngược lại ret_type.rootTree := right_tree.rootTree.
  • Trả về ret_type.

Ví dụ minh họa

import math

class TreeNode:
    def __init__(self, data, left=None, right=None):
        self.data = data
        self.left = left
        self.right = right

class returnType:
    def __init__(self):
        self.isPerfect = None
        self.isComplete = None
        self.size = 0
        self.rootTree = None

def getHeight(size):
    return int(math.ceil(math.log(size + 1) / math.log(2)))

def checkCompleteness(root):
    ret_type = returnType()
    if root is None:
        ret_type.isPerfect = True
        ret_type.isComplete = True
        ret_type.size = 0
        ret_type.rootTree = None
        return ret_type
    left_tree = checkCompleteness(root.left)
    right_tree = checkCompleteness(root.right)
    if (left_tree.isPerfect == True and right_tree.isComplete == True and
        getHeight(left_tree.size) == getHeight(right_tree.size)):
        ret_type.isComplete = True
        ret_type.isPerfect = right_tree.isPerfect
        ret_type.size = left_tree.size + right_tree.size + 1
        ret_type.rootTree = root
        return ret_type
    if (left_tree.isComplete == True and right_tree.isPerfect == True and
        getHeight(left_tree.size) == getHeight(right_tree.size) + 1):
        ret_type.isComplete = True
        ret_type.isPerfect = False
        ret_type.size = left_tree.size + right_tree.size + 1
        ret_type.rootTree = root
        return ret_type
    ret_type.isPerfect = False
    ret_type.isComplete = False
    ret_type.size = max(left_tree.size, right_tree.size)
    if left_tree.size > right_tree.size:
        ret_type.rootTree = left_tree.rootTree
    else:
        ret_type.rootTree = right_tree.rootTree
    return ret_type

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end=', ')
        print_tree(root.right)

root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)
ans = checkCompleteness(root)
print("Size:", ans.size)
print("Inorder Traversal:", end='')
print_tree(ans.rootTree)

Đầu vào

root = TreeNode(50)
root.left = TreeNode(30)
root.right = TreeNode(60)
root.left.left = TreeNode(5)
root.left.right = TreeNode(20)
root.right.left = TreeNode(45)
root.right.right = TreeNode(70)
root.right.left.left = TreeNode(10)

Đầu ra

Size: 4
Inorder Traversal: 10, 45, 60, 70,