《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。
// TheRealBinaryTreeOfMine.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<string>
#include<stack>
#include<queue>
#include<iostream>
#include<math.h>
using namespace std;
class BinaryNode{
public:
char date;
BinaryNode * leftchild;
BinaryNode * rightchild;
BinaryNode(){
date = 0;
leftchild = NULL;
rightchild = NULL;
}
BinaryNode(char ch){
date = ch;
leftchild = NULL;
rightchild = NULL;
}
};
int first_or_last(char a, char b); //判断两个运算符的优先级；
bool isOP(char ch); //判断该字符是否属于操作符； BinaryNode* Build_BinaryTree(BinaryNode* &BT, string str);//根据中缀表达式构建一颗二叉树； void Last(BinaryNode *bt); //后序遍历二叉树（递归）；
void First(BinaryNode *bt); //先序遍历二叉树（递归）；
void Inn(BinaryNode *bt); //中序遍历二叉树（递归）；
string Exp_turn(string s); //后缀表达式转换成中缀表达式；
string Exp_turn_and_turn(string s); //前缀表达式转换为中缀表达式；
int choice(char c, char d); //判断表达式属于什么类型的表达式（中缀，后缀，前缀）；
void Print(BinaryNode *bt); //打印二叉树（层序遍历，层层打印二叉树）；
int first_or_last(char a, char b){
if (a == '/' || a == '*'){
if (b == '+' || b == '-')
return 1;
if (b == '/' || b == '*')
return 0;
else
return 0;
}
if (a == '+' || a == '-'){
if (b == '+' || b == '-')
return 0;
if (b == '/' || b == '*')
return 0;
else
return 0;
}
else