数据结构怎么还原中序表达式的二叉树a+b*c-d-e/f 为中序表达式,如题,应该有什么规则,请详细一点,最好有步骤图,上面的问题已解决.如果只知道后缀表达式可以还原二叉树吗
来源：学生作业帮助网 编辑：六六作业网 时间：2024/11/24 09:55:42
数据结构怎么还原中序表达式的二叉树a+b*c-d-e/f 为中序表达式,如题,应该有什么规则,请详细一点,最好有步骤图,上面的问题已解决.如果只知道后缀表达式可以还原二叉树吗
数据结构怎么还原中序表达式的二叉树
a+b*c-d-e/f 为中序表达式,如题,应该有什么规则,请详细一点,最好有步骤图,
上面的问题已解决.如果只知道后缀表达式可以还原二叉树吗
数据结构怎么还原中序表达式的二叉树a+b*c-d-e/f 为中序表达式,如题,应该有什么规则,请详细一点,最好有步骤图,上面的问题已解决.如果只知道后缀表达式可以还原二叉树吗
根据后缀表达式构造相应的二叉树的算法可如下（先假定‘-’只作为减号运算符,而不存在一元运算的‘-’）.
（1）初始化一个空栈s；
（2）从表达式中读入一个字符到ch；
（3）如果ch为字符串结束符,则转到（7）；
（4）如果ch为操作数,则构造一个值为ch的叶子结点leaf,将leaf进栈,转到（6）；
（5）如果ch为操作符,则构造一个值为ch的分支结点p：
（a）如果栈不空,将栈顶元素出栈到_rchild,并让p->rchild=_rchild.否则算法结束,返回转换失败；
（b）如果栈不空,将栈顶元素出栈到_lchild,并让p->lchild=_lchild,否则算法结束,返回转换失败；
（c）将p进栈；
（6）从表达式中读入下一个字符至ch,转到（3）.
（7）如果栈空,返回失败；否则将栈顶元素出栈到root；此时如果栈空,则root即为根,返回成功；否则返回失败.
C++伪代码可如下：
Stack stack;
stack.Init( );
cin>>ch;
while(ch != '\0'){
if(ch Is OperData){
Node* leaf = new Node(ch);
stack.Push(leaf);
}
else{
Node* p = new Node(ch);
if(stack.IsEmpty( )) return NULL;
Node* _rchild = stack.Pop( );
p->rchild = _rchild;
if(stack.IsEmpty( )) return NULL;
Node* _lchild = stack.Pop( );
p->lchild = _lchild;
stack.Push(p);
}
cin >> ch;
}
if(stack.IsEmpty()) return NULL;
root = stack.Pop( );
if(!stack.IsEmpty( )) return NULL;
return root;