(2 + 3) * 4 = 20变成二叉树
时间: 2024-03-25 11:39:13 浏览: 6
将表达式 "(2 + 3) * 4" 转换为后缀表达式为 "2 3 + 4 *",按照上述步骤构建二叉树,得到以下结构:
```
*
/ \
+ 4
/ \
2 3
```
这个二叉树的计算结果为 20。在计算时,从根节点开始遍历,遇到操作数时将其压入栈中,遇到运算符时从栈中弹出两个操作数进行计算,然后将计算结果压入栈中。最后,栈中只剩下一个元素,即为计算结果。
相关问题
int main(){ cout << "请输入二叉树的先序遍历序列(空节点用-1表示):" << endl; TreeNode* root = buildTree(); cout << "后序遍历结果为:" << endl; postorderTraversal(root); return 0;}用层次遍历该二叉树
您可以使用以下代码来进行二叉树的层次遍历:
```
void levelOrder(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
```
您只需要在原有的代码中添加以下一行代码即可:
```
levelOrder(root);
```
具体来说,您的代码会变成这样:
```
int main(){
cout << "请输入二叉树的先序遍历序列(空节点用-1表示):" << endl;
TreeNode* root = buildTree();
cout << "后序遍历结果为:" << endl;
postorderTraversal(root);
cout << "层次遍历结果为:" << endl;
levelOrder(root);
return 0;
}
```
这样,您的代码就会先进行后序遍历,然后进行层次遍历。
#include<iostream>using namespace std;struct TreeNode{ int val; TreeNode* left; TreeNode* right; TreeNode(int v): val(v), left(NULL), right(NULL) {}};TreeNode* buildTree(){ int val; cin >> val; if(val == -1) // 空节点 return NULL; TreeNode* root = new TreeNode(val); root->left = buildTree(); root->right = buildTree(); return root;}void inorderTraversal(TreeNode* root){ if(root == NULL) return; inorderTraversal(root->left); // 中序遍历左子树 cout << root->val << " "; // 输出当前节点 inorderTraversal(root->right); // 中序遍历右子树}int main(){ cout << "请输入二叉树的先序遍历序列(空节点用-1表示):" << endl; TreeNode* root = buildTree(); cout << "中序遍历结果为:" << endl; inorderTraversal(root); return 0;}用层次遍历搞二叉树
您可以使用以下代码来进行二叉树的层次遍历:
```
void levelOrder(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
```
您只需要在原有的代码中添加以下一行代码即可:
```
levelOrder(root);
```
具体来说,您的代码会变成这样:
```
#include<iostream>
#include<queue>
using namespace std;
struct TreeNode{
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int v): val(v), left(NULL), right(NULL) {}
};
TreeNode* buildTree(){
int val;
cin >> val;
if(val == -1) // 空节点
return NULL;
TreeNode* root = new TreeNode(val);
root->left = buildTree();
root->right = buildTree();
return root;
}
void inorderTraversal(TreeNode* root){
if(root == NULL)
return;
inorderTraversal(root->left); // 中序遍历左子树
cout << root->val << " "; // 输出当前节点
inorderTraversal(root->right); // 中序遍历右子树
}
void levelOrder(TreeNode* root) {
if (!root) {
return;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
cout << node->val << " ";
if (node->left) {
q.push(node->left);
}
if (node->right) {
q.push(node->right);
}
}
}
int main(){
cout << "请输入二叉树的先序遍历序列(空节点用-1表示):" << endl;
TreeNode* root = buildTree();
cout << "中序遍历结果为:" << endl;
inorderTraversal(root);
cout << "\n层次遍历结果为:" << endl;
levelOrder(root);
return 0;
}
```
这样,您的代码就会先进行中序遍历,然后进行层次遍历。