在Python中,我们可以使用树的数据结构来表示字符串数据。以下是一个示例代码:
class TreeNode:
def __init__(self, val):
self.val = val
self.left = None
self.right = None
def build_tree(string):
# 使用递归函数构建树
def helper(index):
# 如果索引超出字符串长度或者当前字符为括号之外的字符,则返回None
if index >= len(string) or string[index] != '(':
return None
# 创建一个新的节点
node = TreeNode('')
value = ''
index += 1
# 提取节点的值
while index < len(string) and string[index] != '(' and string[index] != ')':
value += string[index]
index += 1
node.val = value
# 递归构建左子树
if index < len(string) and string[index] == '(':
node.left, index = helper(index)
# 递归构建右子树
if index < len(string) and string[index] == '(':
node.right, index = helper(index)
index += 1
return node, index
# 调用辅助函数构建树
root, _ = helper(0)
return root
def preorder_traversal(root):
# 先序遍历树
if root:
print(root.val)
preorder_traversal(root.left)
preorder_traversal(root.right)
# 测试代码
string = "(A(B(C)(D))(E(F)))"
root = build_tree(string)
preorder_traversal(root)
这段代码使用递归的方式构建树。给定一个字符串表示的树,我们从根节点开始构建。我们首先遍历字符串,遇到左括号时,创建一个新的节点,并提取节点的值。然后递归构建左子树和右子树。最后返回根节点。然后我们可以使用先序遍历来验证构建的树是否正确。