Skip to content
The Chat Archive
gpt-3.5-turbo-0301· OpenAI WildChat-4.8M (AI2)

编一个程序,读入先序遍历字符串,根据此字符串建立一棵二叉树(以指针方式存储),请注意的是,我们保证该树一定是表达式树(见教材5.2…

  1. User

    编一个程序,读入先序遍历字符串,根据此字符串建立一棵二叉树(以指针方式存储),请注意的是,我们保证该树一定是表达式树(见教材5.2 5.8)。\n\n例如下面的先序遍历字符串:\n\n+ 13 # # * 5 # # 9 # #\n\n运算符只可能是加减乘除,数值为小于等于100,各结点用空格分开,其中“#”代表空树。\n\n\n\n建立起此二叉树以后,再按要求输出二叉树。\n\n\n\n输入\n\n输入由多组测试数据组成。\n\n\n\n每组数据包含一行字符串,即表达式树的先序遍历序列,字符串长度大于0且不超过100。\n\n\n\n输出\n\n对于每组数据,输出一行,内容是该表达式树的全括号表达式,见示例。\n\n样例输入 Copy\n\n+ 13 # # * 5 # # 9 # #* + 13 # # 5 # # 9 # #\n\n样例输出 Copy\n\n(13+(5*9))((13+5)*9)

  2. Assistant

    #include #include #include using namespace std;

    struct TreeNode{ //二叉树结构体 char val; TreeNode* left; TreeNode* right; TreeNode(char x) : val(x), left(NULL), right(NULL) {} };

    TreeNode* createTree(string s, int& index){ //递归建树 if(s[index] == '#'){ index++; return NULL; } TreeNode* root = new TreeNode(s[index]); index++; root -> left = createTree(s, index); root -> right = createTree(s, index); return root; }

    void inorder(TreeNode* root, string& res){ //递归中序遍历,将表达式存入res中 if(!root) return; if(root -> left && (root -> val == '' || root -> val == '/')){ res += '('; inorder(root -> left, res); res += ')'; } else inorder(root -> left, res); res += root -> val; if(root -> right && (root -> val == '' || root -> val == '/')){ res += '('; inorder(root -> right, res); res += ')'; } else inorder(root -> right, res); }

    int main(){ string s; //存储先序遍历的字符串 while(getline(cin, s)){ stack<TreeNode*> stk; int index = 0; TreeNode* root = createTree(s, index); //建树 string res = ""; inorder(root, res); //中序遍历 cout << res << endl; } return 0; }

  3. User

    用c语言实现

  4. Assistant

    由于C语言没有STL库,需要手写一个栈结构来辅助建树和中序遍历。下面是代码: