遍历持有自定义对象的二叉搜索树,可以使用递归或迭代的方式进行。以下是使用递归和迭代的示例代码:
递归方法:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal_recursive(root):
if root is None:
return []
result = []
result.extend(inorder_traversal_recursive(root.left))
result.append(root.value)
result.extend(inorder_traversal_recursive(root.right))
return result
# 示例用法
# 创建二叉树
root = TreeNode(5)
node1 = TreeNode(3)
node2 = TreeNode(7)
node3 = TreeNode(2)
node4 = TreeNode(4)
node5 = TreeNode(6)
node6 = TreeNode(8)
root.left = node1
root.right = node2
node1.left = node3
node1.right = node4
node2.left = node5
node2.right = node6
# 遍历二叉搜索树
result = inorder_traversal_recursive(root)
print(result) # 输出 [2, 3, 4, 5, 6, 7, 8]
迭代方法:
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def inorder_traversal_iterative(root):
if root is None:
return []
result = []
stack = []
current = root
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.value)
current = current.right
return result
# 示例用法同上
# 遍历二叉搜索树
result = inorder_traversal_iterative(root)
print(result) # 输出 [2, 3, 4, 5, 6, 7, 8]
以上代码示例实现了遍历持有自定义对象的二叉搜索树,分别使用递归和迭代的方式实现了中序遍历。可以根据需要选择递归或迭代的方法进行遍历。
下一篇:遍历传递给类的列表