括号表示法输出二叉树

括号表示法是一种将二叉树结构以字符串的形式表示出来的方法。在括号表示法中，每个节点会用一对括号表示，其中左括号表示该节点的子节点开始，右括号表示该节点的子节点结束。具体来说，如果一个节点没有子节点，那么它会被表示为一个只包含左括号的字符串；如果它只有左子节点，那么它会被表示为包含左右括号和左子节点的字符串；如果它只有右子节点，那么它会被表示为包含左右括号和右子节点的字符串；如果它既有左子节点又有右子节点，那么它会被表示为包含左右括号、左子节点和右子节点的字符串。

下面是一个例子，展示如何使用括号表示法输出一棵二叉树：

A
/ \
B C
/ \
D E

这棵二叉树的括号表示法为：(A(B()())(C(D()())(E()())))。

相关问题

1 二叉树的二叉链表存储结构及基本算法的设计与实现 （1）二叉树的创建 （2）二叉树的销毁 （3）二叉树的遍历（先序遍历、中序遍历、后序遍历和层次遍历） （4）用括号表示法输出二叉树模块图

### 二叉树的二叉链表存储结构

在计算机科学中，二叉树是一种重要的数据结构。为了有效地管理和操作二叉树，通常采用二叉链表作为其存储方式之一。每个结点由三部分组成：指向左孩子的指针、数据域和指向右孩子的指针。

#### 结构定义

typedef struct BiTNode {
    char data;           // 数据域
    struct BiTNode *lchild, *rchild; // 左右孩子指针
}BiTNode,*BiTree;

### 基本算法设计与实现

#### 创建二叉树
通过前序序列可以唯一确定一棵二叉树。这里提供一种基于字符输入构建的方法：

void CreateBiTree(BiTree &T){
    char ch;
    cin >> ch;
    if(ch == '#') T = NULL;
    else{
        T = new BiTnode;
        T->data = ch;
        CreateBiTree(T->lchild);     // 构建左子树
        CreateBiTree(T->rchild);     // 构建右子树
    }
}

#### 销毁二叉树
释放内存空间并使该二叉树为空的过程称为销毁二叉树。

void DestroyBiTree(BiTree &T){
    if (T != nullptr) {              // 若当前节点不为空，则继续处理
        DestroyBiTree(T->lchild);
        DestroyBiTree(T->rchild);
        delete T;                    // 删除此节点所占的空间
        T = nullptr;                 // 将指针置为NULL防止悬挂指针
    }
}

#### 遍历方法

##### 先序遍历（Preorder Traversal）
按照访问根节点 -> 访问左子树 -> 访问右子树的方式依次递归地遍历整棵树。

void PreOrderTraverse(BiTree T,void(*Visit)(char)){
    if (T!=nullptr){                // 如果不是空树则执行下面语句
        Visit(T->data);             // 处理根节点的数据
        PreOrderTraverse(T->lchild,Visit);// 对左子树做相同的操作
        PreOrderTraverse(T->rchild,Visit);// 对右子树做相同的操作
    }
}

##### 中序遍历（Inorder Traversal）
遵循访问左子树 -> 访问根节点 -> 访问右子树的原则来遍历整个二叉树。

void InOrderTraverse(BiTree T,void(*Visit)(char)){
    if (T!=nullptr){
        InOrderTraverse(T->lchild,Visit);
        Visit(T->data);
        InOrderTraverse(T->rchild,Visit);
    }
}

##### 后序遍历（Postorder Traversal）
采取先访问左右子树再回溯到父节点进行访问的形式完成遍历过程。

void PostOrderTraverse(BiTree T,void(*Visit)(char)){
    if (T!=nullptr){
        PostOrderTraverse(T->lchild,Visit);
        PostOrderTraverse(T->rchild,Visit);
        Visit(T->data);
    }
}

##### 层次遍历（Level Order Traversal）

层次遍历是指按层顺序逐层扫描各节点，在同一层内自左向右依次读取各个顶点的信息。

#include <queue>
using namespace std;

void LevelOrderTraverse(BiTree T,void (*Visit)(char)) {
    queue<BiTNode*> q;
    if (!T) return ;
    
    q.push(T);

    while(!q.empty()){
        auto node=q.front();
        q.pop();

        Visit(node->data);

        if(node->lchild) q.push(node->lchild);
        if(node->rchild) q.push(node->rchild);
    }
}

#### 使用括号表示法输出二叉树模块图

对于给定的一棵二叉树，可以通过特定格式打印出来以便于观察其形态特征。具体做法如下所示:

string TreeToString(const BiTree& root) {
    if(root==nullptr)return "()";
    string res="("+to_string(root->data)+",";
    res+=TreeToString(root->lchild);
    res=res+",";
    res+=TreeToString(root->rchild);
    res+=")";
    return res;
}

// 打印函数调用例子
cout<<TreeToString(tree)<<endl;

上述代码实现了将二叉树转换成字符串形式的功能，其中`()`代表空子树；`(A,B,C)`分别对应着根节点及其左右两个分支的内容[^1]。

括号表示法创建二叉树

括号表示法是一种二叉树的表示方法，可以通过该方法创建一棵二叉树。具体步骤如下：

1. 创建一个空栈，用于存储节点。
2. 从左到右遍历括号表示法中的每个字符，如果当前字符是左括号，则创建一个新节点，并将其作为上一个节点的左子节点或右子节点，具体取决于上一个节点的状态。然后将该节点入栈。
3. 如果当前字符是右括号，则弹出栈顶节点，并将其作为上一个节点的右子节点。如果栈为空，则说明已经遍历完整棵树。
4. 重复步骤2和3，直到遍历完整个括号表示法。

下面是一个Python实现的例子：

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

def createTree(s):
    stack = []
    root = None
    for c in s:
        if c == '(':
            if root:
                node = TreeNode()
                if not root.left:
                    root.left = node
                else:
                    root.right = node
                stack.append(root)
                root = node
            else:
                root = TreeNode()
                stack.append(root)
        elif c == ')':
            if stack:
                root = stack.pop()
        else:
            root.val = int(c)
    return root

# 示例
s = "(1(2(4)(5))(3(6)))"
root = createTree(s)
print(root.val)  # 输出：1