树结构及其算法-二叉运算树

目录

树结构及其算法-二叉运算树

C++代码

树结构及其算法-二叉运算树

二叉树的应用实际上相当广泛，例如表达式之间的转换。可以把中序表达式按运算符优先级的顺序建成一棵二叉运算树（Binary Expression Tree，或称为二叉表达式树）。之后按二叉树的特性进行前、中、后序的遍历，即可得到前、中、后序表达式，建立的方法可根据以下两种规则来进行操作：

1. 考虑表达式中运算符的结合性与优先权，再适当地加上括号。
2. 由最内层的括号逐步向外，利用运算符当树根，左边操作数当左子树，右边操作数当右子树，其中优先权最低的运算符作为此二叉运算树的树根。

C++代码

#include<iostream>
using namespace std;struct TreeNode {int data;TreeNode* leftNode;TreeNode* rightNode;TreeNode() {this->data = ' ';this->leftNode = nullptr;this->rightNode = nullptr;}TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {this->data = tempData;this->leftNode = tempLeftNode;this->rightNode = tempRightNode;}
};namespace Tree {TreeNode* CreateExpression(char* sequence, int index, int arraySize) {TreeNode* _TreeNode;if (sequence[index] == ' ' || index >= arraySize)return nullptr;else{_TreeNode = new TreeNode((int)sequence[index]);_TreeNode->leftNode = CreateExpression(sequence, 2 * index, arraySize);_TreeNode->rightNode = CreateExpression(sequence, 2 * index + 1, arraySize);return _TreeNode;}}void Preorder(TreeNode* tempTree) {if (tempTree != nullptr) {cout << (char)tempTree->data << " ";Preorder(tempTree->leftNode);Preorder(tempTree->rightNode);}}void Inorder(TreeNode* tempTree) {if (tempTree != nullptr) {Inorder(tempTree->leftNode);cout << (char)tempTree->data << " ";Inorder(tempTree->rightNode);}}void Postorder(TreeNode* tempTree) {if (tempTree != nullptr) {Postorder(tempTree->leftNode);Postorder(tempTree->rightNode);cout << (char)tempTree->data << " ";}}int Condition(char tempOperator, int num1, int num2) {switch (tempOperator){case '*':return (num1 * num2);case '/':return (num1 / num2);case '+':return (num1 + num2);case '-':return (num1 - num2);case '%':return (num1 % num2);}}int Answer(TreeNode* tempTreeNode) {int num1;int num2;if (tempTreeNode->rightNode == nullptr && tempTreeNode->leftNode == nullptr)return tempTreeNode->data - 48;else {num1 = Answer(tempTreeNode->leftNode);num2 = Answer(tempTreeNode->rightNode);return Condition((char)tempTreeNode->data, num1, num2);}}
};int main() {char data1[]{ ' ', '+', '*', '%', '6', '3', '9', '5' };TreeNode* treeNode;treeNode = Tree::CreateExpression(data1, 1, 8);cout << "前序遍历：" << endl;Tree::Preorder(treeNode);cout << endl;cout << "中序遍历：" << endl;Tree::Inorder(treeNode);cout << endl;cout << "后序遍历：" << endl;Tree::Postorder(treeNode);cout << endl;cout << "二叉运算树结果值：" << endl;cout << Tree::Answer(treeNode) << endl;return 0;
}

结果输出