《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。
return 0;
}
bool isOP(char ch)
{
string OP = { '+', '-', '*', '/', '(', ')' };
for (int i = 0; i < 6; i++){
if (ch == OP[i])
return true;
}
return false;
}
BinaryNode* Build_BinaryTree(BinaryNode* &BT, string str){
queue <BinaryNode*> aQ;
BinaryNode * root = BT;
if (str[0] == '('){
root = new BinaryNode(str[2]);
BT = new BinaryNode(str[1]);
BinaryNode *R = root;
aQ.push(BT);
int j = 3;
while (str[j] != '\0')
{
if (!isOP(str[j]))
{
BT = new BinaryNode(str[j]);
aQ.push(BT);
j++;
}
else
{
if (str[j] == ')' || str[j] == '(')
{
}
else
{
BT = new BinaryNode(str[j]);
root->leftchild = aQ.front();
//cout << root->leftchild->date;
root->rightchild = BT;
//cout << root->rightchild->date;
aQ.pop();
root = BT;
}
j++;
}
}
root->leftchild = aQ.front();
//cout << root->leftchild->date;
aQ.pop();
root->rightchild = aQ.front();
//cout << root->rightchild->date;
aQ.pop();
return R;
}
else{
root = new BinaryNode(str[1]);
BT = new BinaryNode(str[0]);
BinaryNode *R = root;
aQ.push(BT);