免费虚拟主机免费空间,河北网站seo地址,全flash网站模板,专业网站设计制作价格目录
树结构及其算法-二叉运算树
C代码 树结构及其算法-二叉运算树
二叉树的应用实际上相当广泛#xff0c;例如表达式之间的转换。可以把中序表达式按运算符优先级的顺序建成一棵二叉运算树#xff08;Binary Expression Tree#xff0c;或称为二叉表达式树#xff09;…目录
树结构及其算法-二叉运算树
C代码 树结构及其算法-二叉运算树
二叉树的应用实际上相当广泛例如表达式之间的转换。可以把中序表达式按运算符优先级的顺序建成一棵二叉运算树Binary Expression Tree或称为二叉表达式树。之后按二叉树的特性进行前、中、后序的遍历即可得到前、中、后序表达式建立的方法可根据以下两种规则来进行操作
考虑表达式中运算符的结合性与优先权再适当地加上括号。由最内层的括号逐步向外利用运算符当树根左边操作数当左子树右边操作数当右子树其中优先权最低的运算符作为此二叉运算树的树根。
C代码
#includeiostream
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;
}
结果输出
