Hdu1805-Expression(表达式树模版题+层序遍历树+栈的基本应用)

2018-11-23-02:27:37

原题链接

题目描述:

    题目一目了然。

本题思路:

    本题很容易能想到是构建表达式树然后按照层序逆序输出即可。

AC代码:

 #include <cstdio>
#include <cstring>
#include <stack>
#include <queue>
#include <iostream>
using namespace std; typedef char TElemType;
typedef struct BiNode {
TElemType Elem;
struct BiNode *Left_Child;
struct BiNode *Right_Child;
} BiNode, *BiTree;
bool IsOperator(char Elem);
void PrintBiTree(BiTree T);
BiTree ConstructingExpressionTree(string Expression); int main() {
BiTree T;
string Expression;
cin >> Expression;
T=ConstructingExpressionTree(Expression);
PrintBiTree(T);
return ;
}
bool IsOperator(char Elem) {
return (Elem == '+' || Elem == '-' || Elem == '*' || Elem == '/');
} BiTree ConstructingExpressionTree(string Expression) {
stack<BiTree>Operand;
for(int i = ; i < Expression.length(); i++) {
BiTree Child;
if(!IsOperator(Expression[i])) {
Child = new BiNode;
Child->Elem = Expression[i];
Child->Right_Child = NULL;//Operand一定是叶结点
Child->Left_Child = NULL;
Operand.push(Child);
}
if(IsOperator(Expression[i])) {
Child = new BiNode;
Child->Elem = Expression[i];
Child->Right_Child = Operand.top();
Operand.pop();
Child->Left_Child = Operand.top();
Operand.pop();
Operand.push(Child);//将构造好的子表达式树的结点压入栈,便于最后汇入总表达式树
}
}
return Operand.top();
} void PrintBiTree(BiTree T){
//按照层序遍历输出二叉树
if(T==NULL) return;
queue<BiTree>QueueTreeNode;
QueueTreeNode.push(T);//首先将二叉树的头结点放入队列
while(!QueueTreeNode.empty()){//如果队列为空则结束遍历
BiTree QueueNode=QueueTreeNode.front();//每次访问队列的第一个元素并将其弹出
QueueTreeNode.pop();
cout<<QueueNode->Elem<<' ';
if(QueueNode->Left_Child)//将第一个元素的左右子树的结点都放入队列
QueueTreeNode.push(QueueNode->Left_Child);
if(QueueNode->Right_Child)
QueueTreeNode.push(QueueNode->Right_Child);
}
}

本题应熟记知识点:表达式树的构建与层序遍历二叉树。

1.构建表达式树

    ① 算法描述:

      遍历后缀表达式,如果符号是Operand,那么我们就建立一个单结点树并将一个指向他的指针推入栈中,如果符号是Operator,那么我们就从栈中弹出指向两棵树T1和T2的那两个指针(T1的先弹出)并形成一颗新

    的树,该树的根就是Operator,他的左右儿子分别指向T2和T1,然后将指向这颗新树的指针压入栈中。

    ② 代码:

 BiTree ConstructingExpressionTree(string Expression) {
stack<BiTree>Operand;
for(int i = ; i < Expression.length(); i++) {
BiTree Child;
if(!IsOperator(Expression[i])) {
Child = new BiNode;
Child->Elem = Expression[i];
Child->Right_Child = NULL;//Operand一定是叶结点
Child->Left_Child = NULL;
Operand.push(Child);
}
if(IsOperator(Expression[i])) {
Child = new BiNode;
Child->Elem = Expression[i];
Child->Right_Child = Operand.top();
Operand.pop();
Child->Left_Child = Operand.top();
Operand.pop();
Operand.push(Child);//将构造好的子表达式树的结点压入栈,便于最后汇入总表达式树
}
}
return Operand.top();
} bool IsOperator(char Elem) {
return (Elem == '+' || Elem == '-' || Elem == '*' || Elem == '/');
}

2.二叉树的层序遍历

    ① 算法思路:

       代码里都有。

    ② 代码:

     

 void PrintBiTree(BiTree T) {
//按照层序遍历输出二叉树
if(T == NULL) return;
queue<BiTree>QueueTreeNode;
QueueTreeNode.push(T);//首先将二叉树的头结点放入队列
while(!QueueTreeNode.empty()) { //如果队列为空则结束遍历
BiTree QueueNode = QueueTreeNode.front(); //每次访问队列的第一个元素并将其弹出
QueueTreeNode.pop();
cout << QueueNode->Elem << ' ';
if(QueueNode->Left_Child)//将第一个元素的左右子树的结点都放入队列
QueueTreeNode.push(QueueNode->Left_Child);
if(QueueNode->Right_Child)
QueueTreeNode.push(QueueNode->Right_Child);
}
}
上一篇:三种方法实现调用Restful接口


下一篇:JQuery 操作对象的属性值