二叉树与表达式

将通过二叉链表实现的表达式二叉树进行输出,同时计算出结果。

要求:

1)二叉树建立时,使用先序建立;

2)四个运算符包括:+, -, *, /;

3 ) 在输出时,遇到优先级问题时,相应的括号也要输出。

提示:

1)递归执行下列步骤即可求值:先分别求出左子树和右子树表示的子表达式的值,最后根据根结点的运算符的要求,计算出表达式的最后结果。

2)二叉树的中序遍历序列与原算术表达式基本相同,但是需要将中序序列加上括号,即当根结点运算符优先级高于左子树(或右子树)根结点运算符时,就需要加括号。

代码如下:

#include <iostream>
using namespace std;
class BinaryTree;
class BinTreeNode{//结点类定义
    friend class BinaryTree;
private:
    BinTreeNode *leftChild,*rightChild;//左右子女链域
    char data;//数据域
public:
    BinTreeNode(){leftChild=NULL;rightChild=NULL;}
    BinTreeNode(char x,BinTreeNode *left=NULL,BinTreeNode *right=NULL)
    {//构造函数
        data=x;
        leftChild=left;
        rightChild=right;
    }
    ~BinTreeNode(){}//析构函数
};
class BinaryTree{//二叉树的定义
private:
    BinTreeNode *root;//二叉树的根指针
    char RefValue;//数据输入停止标志
    void CreateBinTree(BinTreeNode *&subTree);
    void inOrder(BinTreeNode *subTree);//中序遍历
    int operation(BinTreeNode *subTree);//计算表达式
public:
    BinaryTree():root(NULL),RefValue('@'){}
    BinaryTree(char value){RefValue=value;root=NULL;}
    void CreateBinTree(){
        CreateBinTree(root);
    }
    void inOrder(){inOrder(root);}//中序遍历
    int operation(){return operation(root);}//计算表达式
};
void BinaryTree::CreateBinTree(BinTreeNode *&subTree)//二叉树的建立
{
    char item;
    cin>>item;
    if(item!=RefValue)
    {
        subTree=new BinTreeNode(item);
        CreateBinTree(subTree->leftChild);
        CreateBinTree(subTree->rightChild);
    }
    else subTree=NULL;
}

bool judge(char op1,char op2)
{
    if((op1=='*'||op1=='/')&&(op2=='+'||op2=='-'))
        return true;
    else
        return false;
}
void BinaryTree::inOrder(BinTreeNode *subTree)//中序遍历
{
    if(subTree!=NULL)
    {
        if(subTree->rightChild!=NULL&&judge(subTree->data,subTree->rightChild->data))
        {
            inOrder(subTree->leftChild);
            cout<<subTree->data;
            cout<<'(';
            inOrder(subTree->rightChild);
            cout<<')';
        }
        else
        {
            inOrder(subTree->leftChild);
            cout<<subTree->data;
            inOrder(subTree->rightChild);
        }
    }
}

int BinaryTree::operation(BinTreeNode *subTree)//计算表达式
{
    if(subTree!=NULL)
    {
        switch(subTree->data)
        {
        case '+':
            return operation(subTree->leftChild)+operation(subTree->rightChild);
            break;
        case '-':
            return operation(subTree->leftChild)-operation(subTree->rightChild);
            break;
        case '*':
            return operation(subTree->leftChild)*operation(subTree->rightChild);
            break;
        case '/':
            return operation(subTree->leftChild)/operation(subTree->rightChild);
            break;
        default:
            return int(subTree->data-'0');
        }
    }
}
int main()
{
    BinaryTree A;
    A.CreateBinTree();
    A.inOrder();
    cout<<'='<<A.operation()<<endl;
    return 0;
}


You may also like...

发表评论

电子邮件地址不会被公开。 必填项已用*标注