用递归和广义表创建二叉树

可以使用广义表表示二叉树，二叉树的广义表表示法定义如下：

- 空二叉树用空表表示。
- 非空二叉树用一个三元组表示：(data, left_child, right_child)，其中data为根节点的数据，left_child和right_child分别为左子树和右子树的广义表表示。

递归的思路是：先读入三元组的第一个元素作为根节点的数据，然后递归读入左子树和右子树的广义表表示。左子树和右子树的广义表表示也是三元组，所以可以继续递归下去。

下面是使用 Python 实现的代码：

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

def create_tree(s):
    if s[0] == '()': # 空树
        return None
    # 获取根节点的值
    i = 0
    while s[i] != '(':
        i += 1
    val = int(s[:i])
    # 递归创建左子树和右子树
    j = i + 1
    cnt = 1 # 左右括号的数量
    while cnt != 0:
        if s[j] == '(':
            cnt += 1
        elif s[j] == ')':
            cnt -= 1
        j += 1
    left = create_tree(s[i+1:j])
    right = create_tree(s[j+1:-1])
    return TreeNode(val, left, right)

# 测试代码
s = '1(2(4()())(5()()))(3(6()())())'
root = create_tree(s)

在上面的代码中，TreeNode 表示二叉树节点的类，create_tree 函数用于创建二叉树。函数的参数 s 是二叉树的广义表表示，返回值是根节点。