在 Python 中查找给定二叉树中的最大完整子树
pythonserver side programmingprogramming更新于 2025/10/17 3:24:17
假设我们有一棵二叉树；我们必须找到这棵二叉树中最大完整子树的大小。我们知道，如果所有级别都完全填充而没有最终级别，并且最终级别尽可能地保留所有键，则完全二叉树是二叉树。
因此，如果输入如下
则输出将为 4 作为大小，中序遍历将为 10、45、60、70，
为了解决这个问题，我们将遵循以下步骤 −
- 使用几个参数定义返回类型，例如 isComplete、isPerfect，这些参数最初为 false，然后是 size 和 rootTree，size 最初为 0，rootTree 为 null。
- ret_type := returnType
- 如果 root 为空，则
- ret_type.isPerfect := True
- ret_type.isComplete := True
- ret_type.size := 0
- ret_type.rootTree := None
- 返回 ret_type
- left_tree := checkCompleteness(root.left)
- right_tree := checkCompleteness(root.right)
- 如果 left_tree.isPerfect 为 True 且 right_tree.isComplete 为 True 且左右树的高度相同，则
- ret_type.isComplete := True
- ret_type.isPerfect := right_tree.isPerfect
- ret_type.size := left_tree.size + right_tree.size + 1
- ret_type.rootTree := root
- 返回 ret_type
- 如果 (left_tree.isComplete 为 True 且 right_tree.isPerfect 为 True 且左右树的高度相同，则
- ret_type.isComplete := True
- ret_type.isPerfect := False
- ret_type.size := left_tree.size + right_tree.size + 1
- ret_type.rootTree := root
- 返回 ret_type
- ret_type.isPerfect := False
- ret_type.isComplete := False
- ret_type.size := left_tree.size 和 right_tree.size 的最大值
- 如果 left_tree.size > right_tree.size，则
- ret_type.rootTree := left_tree.rootTree
- 否则，
- ret_type.rootTree := right_tree.rootTree
- 返回 ret_type
Python
让我们看看下面的实现以便更好地理解 −
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 == 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)
输入
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)
Output:
Size: 4 Inorder Traversal: 10, 45, 60, 70,
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/
