树的广义表表示法例题

树的广义表表示法是一种用圆圈和方框分别表示表和单元素，并用线段把表和它的元素连接起来的表示方法。其中树根结点代表整个广义表，各层树枝结点代表相应的子表，树叶结点代表单元素或空表。下面以一个例题来介绍树的广义表表示法的建立过程。

假设有一棵二叉树，其广义表表示法为：1(2(4,5),3(6(8),7))。根据广义表表示法，我们可以得到以下树形结构：

      1
     / \
    2   3
   / \  / \
  4   5 6  7
       /
      8

根据广义表表示法，我们可以按照以下步骤建立二叉树：

1. 如果遇到了"("，说明要对这个结点的左子树进行创建。
2. 如果遇到了")"，说明要对这个结点的父结点进行操作。
3. 如果遇到了","，说明已经创建好了左结点（即现在的T指向的是左结点），要对T的父结点的右结点进行创建。

根据以上步骤，我们可以得到以下Python代码：

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

def createTree(s):
    if not s:
        return None
    stack = []
    root = None
    flag = 0
    for i in range(len(s)):
        if s[i] == '(':
            stack.append(T)
            flag = 1
        elif s[i] == ')':
            stack.pop()
        elif s[i] == ',':
            flag = 2
        else:
            j = i
            while j < len(s) and s[j] != '(' and s[j] != ')' and s[j] != ',':
                j += 1
            node = TreeNode(int(s[i:j]))
            if not root:
                root = node
            if flag == 1:
                stack[-1].left = node
            elif flag == 2:
                stack[-1].right = node
            T = node
            i = j - 1
    return root

以上代码中，我们首先定义了一个TreeNode类，用于表示二叉树的结点。然后我们定义了一个createTree函数，用于根据广义表表示法创建二叉树。在函数中，我们首先判断输入的字符串是否为空，如果为空则直接返回None。然后我们定义了一个栈stack，一个根节点root和一个标志位flag。接下来我们遍历字符串s中的每个字符，如果遇到了"("，则将当前结点T入栈，并将flag设置为1；如果遇到了")"，则将栈顶元素出栈；如果遇到了","，则将flag设置为2；否则，我们就将当前字符到下一个"("、")"或","之间的字符转换为整数，并创建一个新的结点node。如果当前结点T为空，则将root设置为node；如果flag为1，则将node作为T的左子结点；如果flag为2，则将node作为T的右子结点。最后，我们将T设置为node，并将i设置为j-1，以便跳过已经处理过的字符。最后，我们返回根节点root。