C++ 实现二叉树凹入表示法：先序和中序遍历构建树

#include\x20 #include\x20 #include\x20<unordered_map> using\x20namespace\x20std;

//\x20定义二叉树的节点 struct\x20TreeNode\x20{ \x20\x20char\x20val; \x20\x20TreeNode*\x20left; \x20\x20TreeNode*\x20right; \x20\x20TreeNode(char\x20x)\x20:\x20val(x),\x20left(nullptr),\x20right(nullptr)\x20{}};

//\x20构建二叉树 TreeNode*\x20buildTree(string\x20preorder,\x20string\x20inorder)\x20{ \x20\x20if\x20(preorder.empty())\x20{ \x20\x20\x20\x20return\x20nullptr; \x20\x20} \x20\x20char\x20rootVal\x20=\x20preorder[0]; \x20\x20int\x20rootIndex\x20=\x20inorder.find(rootVal); \x20\x20string\x20leftInorder\x20=\x20inorder.substr(0,\x20rootIndex); \x20\x20string\x20rightInorder\x20=\x20inorder.substr(rootIndex\x20+\x201); \x20\x20string\x20leftPreorder\x20=\x20preorder.substr(1,\x20rootIndex); \x20\x20string\x20rightPreorder\x20=\x20preorder.substr(rootIndex\x20+\x201); \x20\x20TreeNode*\x20root\x20=\x20new\x20TreeNode(rootVal); \x20\x20root->left\x20=\x20buildTree(leftPreorder,\x20leftInorder); \x20\x20root->right\x20=\x20buildTree(rightPreorder,\x20rightInorder); \x20\x20return\x20root; }

//\x20打印树的凹入表示法 void\x20printIndentedTree(TreeNode*\x20root,\x20unordered_map<char,\x20int>&\x20nodeLength,\x20int\x20depth)\x20{ \x20\x20if\x20(root\x20==\x20nullptr)\x20{ \x20\x20\x20\x20return; \x20\x20} \x20\x20for\x20(int\x20i\x20=\x200;\x20i\x20<\x20depth;\x20i++)\x20{ \x20\x20\x20\x20cout\x20<<\x20string(nodeLength[root->val],\x20root->val)\x20<<\x20endl; \x20\x20} \x20\x20printIndentedTree(root->left,\x20nodeLength,\x20depth\x20+\x201); \x20\x20printIndentedTree(root->right,\x20nodeLength,\x20depth\x20+\x201); }

int\x20main()\x20{ \x20\x20string\x20preorder,\x20inorder; \x20\x20cin\x20>>\x20preorder\x20>>\x20inorder; \x20\x20 \x20\x20//\x20构建二叉树 \x20\x20TreeNode*\x20root\x20=\x20buildTree(preorder,\x20inorder); \x20\x20 \x20\x20//\x20计算每个节点的长度 \x20\x20unordered_map<char,\x20int>\x20nodeLength; \x20\x20for\x20(char\x20c\x20:\x20inorder)\x20{ \x20\x20\x20\x20if\x20(nodeLength.find(c)\x20==\x20nodeLength.end())\x20{ \x20\x20\x20\x20\x20\x20nodeLength[c]\x20=\x201; \x20\x20\x20\x20}else\x20{ \x20\x20\x20\x20\x20\x20nodeLength[c]++; \x20\x20\x20\x20} \x20\x20} \x20\x20 \x20\x20//\x20打印树的凹入表示法 \x20\x20printIndentedTree(root,\x20nodeLength,\x200); \x20\x20 \x20\x20return\x200; }