《数据结构与算法》上的一道作业题答案,本程序设计二叉树的构建,遍历以及打印等函数,能够实现自动分辨所输入表达式属于什么类型。
int j = 2;
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;
}
}//中缀表达式构建了二叉树函数（消除了‘（’和‘）’）
void Last(BinaryNode *bt){
if (bt){
Last(bt->leftchild);
Last(bt->rightchild);
cout << bt->date;
}
}//后序遍历函数
void First(BinaryNode *bt){
if (bt){
cout << bt->date;
First(bt->leftchild);
First(bt->rightchild);
}
}//先序遍历函数
void Inn(BinaryNode *bt){
if (bt){
Inn(bt->leftchild);
cout << bt->date;
if (bt->rightchild)
{
if (isOP(bt->rightchild->date) && first_or_last(bt->date, bt->rightchild->date) == 1){ cout << "(";