本习题为二叉树的基本运算练习，要求依次实现如下功能： 输入一个使用“括号表示法”表示的二叉树，每个节点的数据为一个字符，请使用二叉链的存储方式构建二叉树b。 使用中序遍历法遍历构建的二叉树，输出中序遍历的序列。 输出该二叉树的高度（深度），其中，根节点作为第1层。 计算该二叉树中所有叶子节点的个数。 将该二叉树的左右子树进行交换，生成一个新的二叉树t。 将新生成的二叉树 t 使用括号表示法表示，并输出该括号表示法的结果。

### 构建二叉树 构建二叉树可以通过多种方式实现，其中一种常见的方式是通过前序遍历序列来构造。假设输入是一个字符串形式的前序遍历序列，可以利用递归来完成二叉树的构建。 以下是基于字符数组的二叉树构建方法： ```cpp #include <iostream> using namespace std; struct TreeNode { char data; TreeNode* left; TreeNode* right; }; TreeNode* createBinaryTree(char*& str) { if (*str == '\0') return nullptr; if (*str == '#') { // '#' 表示空节点 str++; return nullptr; } TreeNode* root = new TreeNode(); root->data = *str++; // 当前字符作为根节点数据 root->left = createBinaryTree(str); // 递归创建左子树 root->right = createBinaryTree(str); // 递归创建右子树 return root; } ``` --- ### 中序遍历 中序遍历是一种按照“左-根-右”的顺序访问二叉树节点的方法。其实现如下： ```cpp void inorderTraversal(TreeNode* root) { if (root != nullptr) { inorderTraversal(root->left); cout << root->data << " "; inorderTraversal(root->right); } } ``` --- ### 高度计算 二叉树的高度是指从根节点到最远叶节点路径上的边数。其计算逻辑为：如果当前节点为空，则高度为0；否则取左右子树的最大高度加1。 ```cpp int calculateHeight(TreeNode* root) { if (root == nullptr) return 0; int leftHeight = calculateHeight(root->left); int rightHeight = calculateHeight(root->right); return max(leftHeight, rightHeight) + 1; } ``` --- ### 统计叶子节点数 叶子节点是没有子节点的节点。统计叶子节点数量的过程类似于计算高度，只需判断当前节点是否为叶子节点即可。 ```cpp int countLeaves(TreeNode* root) { if (root == nullptr) return 0; if (root->left == nullptr && root->right == nullptr) return 1; // 叶子节点 return countLeaves(root->left) + countLeaves(root->right); } ``` --- ### 左右子树交换 交换左右子树的操作非常简单，只需要互换两个指针即可。对于整个二叉树来说，可以用递归的方式来完成这一操作。 ```cpp void swapSubtrees(TreeNode* root) { if (root == nullptr) return; swap(root->left, root->right); // 交换左右子树 swapSubtrees(root->left); // 对新的左子树递归调用 swapSubtrees(root->right); // 对新的右子树递归调用 } ``` --- ### 括号表示法输出 括号表示法是一种常用的二叉树表示方法，通常采用广义表的形式。例如，`A(B(C,D),E)` 表示一个以 A 为根节点的二叉树，B 是它的左子树，E 是它的右子树。 下面是实现括号表示法输出的代码： ```cpp void printParenthesis(TreeNode* root) { if (root == nullptr) return; cout << root->data; if (root->left || root->right) { cout << "("; printParenthesis(root->left); if (root->right) cout << ","; printParenthesis(root->right); cout << ")"; } } ``` --- ### 总结 以上实现了二叉树的基本运算功能，包括但不限于构建二叉树、中序遍历、高度计算、叶子节点统计、左右子树交换以及括号表示法输出[^1]。这些功能覆盖了常见的二叉树操作需求，并提供了清晰易懂的代码实现。 ####