作业帮 > 综合 > 作业

数据结构怎么还原中序表达式的二叉树

来源:学生作业帮 编辑:拍题作业网作业帮 分类:综合作业 时间:2024/03/29 00:31:51
数据结构怎么还原中序表达式的二叉树
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;