C++代码实现【题目描述】树的凹入表示法主要用于树的屏幕或打印输出其表示的基本思想是兄弟间等长一个结点的长度要不小于其子结点的长度。二叉树也可以这样表示假设叶结点的长度为1一个非叶结点的长度等于它的左右子树的长度之和。一棵二叉树的一个结点用一个字母表示无重复输出时从根结点开始：每行输出若干个结点字符相同字符的个数等于该结点长度如果该结点有左子树就递归输出左子树；如果该结点有右子树就递归输出右子树。

#include #include #include <unordered_map> using namespace std;

// 定义二叉树的节点 struct TreeNode { char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(nullptr), right(nullptr) {} };

// 构建二叉树 TreeNode* buildTree(string preorder, string inorder) { if (preorder.empty()) { return nullptr; } char rootVal = preorder[0]; int rootIndex = inorder.find(rootVal); string leftInorder = inorder.substr(0, rootIndex); string rightInorder = inorder.substr(rootIndex + 1); string leftPreorder = preorder.substr(1, rootIndex); string rightPreorder = preorder.substr(rootIndex + 1); TreeNode* root = new TreeNode(rootVal); root->left = buildTree(leftPreorder, leftInorder); root->right = buildTree(rightPreorder, rightInorder); return root; }

// 打印树的凹入表示法 void printIndentedTree(TreeNode* root, unordered_map<char, int>& nodeLength, int depth) { if (root == nullptr) { return; } for (int i = 0; i < depth; i++) { cout << string(nodeLength[root->val], root->val) << endl; } printIndentedTree(root->left, nodeLength, depth + 1); printIndentedTree(root->right, nodeLength, depth + 1); }

int main() { string preorder, inorder; cin >> preorder >> inorder;

// 构建二叉树
TreeNode* root = buildTree(preorder, inorder);

// 计算每个节点的长度
unordered_map<char, int> nodeLength;
for (char c : inorder) {
    if (nodeLength.find(c) == nodeLength.end()) {
        nodeLength[c] = 1;
    } else {
        nodeLength[c]++;
    }
}

// 打印树的凹入表示法
printIndentedTree(root, nodeLength, 0);

return 0;