美文网首页
二叉树的应用----表达式树

二叉树的应用----表达式树

作者: 赫尔特 | 来源:发表于2019-12-30 21:47 被阅读0次

文章目录

\color{#0AAD1A}{何为表达式树}
\color{#0FAC1A}{表达式树实现}
\color{#0FAC1A}{表达式树优化}
\color{#0FAC1A}{Reference}

何为表达式树

1
上图就是一个表达式树（手动滑稽）
下面我会给出把中缀表达式（字符串）转化成表达式树的代码

表达式树实现

作为二叉树的一个应用，这里就用二叉树这种数据结构来实现~

这里有一个重要的知识点，在利用指针实现的二叉树中，叶节点（叶结点）与非叶节点是否使用相同的定义十分重要。使用相同的类可以简化实现，但是可能导致空间上的浪费。

有一些应用只需要叶结点存储数据，还有一些应用要求分支结点（非叶节点）与叶结点存储不同类型的数据。
代码（1）^2用同样的方式实现叶子节点和非叶节点
代码（2）^2用不同的方式实现叶子节点和非叶节点

（感觉（1）不好理解的话可以先看（2））

（1）

// Node implementation with simple inheritance
class VarBinNode { // Node  base class基类
public:
virtual ˜VarBinNode() {}
virtual bool isLeaf() = 0; // Subclasses must implement
};
class LeafNode : public VarBinNode { // Leaf node叶子结点
private:
Operand var; // Operand value
public:
LeafNode(const Operand& val) { var = val; } // Constructor
bool isLeaf() { return true; } // Version for LeafNode
Operand value() { return var; } // Return node value
};
class IntlNode : public VarBinNode { // Internal node非叶子结点
private:
VarBinNode* left; // Left child
VarBinNode* right; // Right child
Operator opx; // Operator value
public:
IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r)
{ opx = op; left = l; right = r; } // Constructor

bool isLeaf() { return false; } // Version for IntlNode

VarBinNode* leftchild() { return left; } // Left child

VarBinNode* rightchild() { return right; } // Right child

Operator value() { return opx; } // Value

};
void traverse(VarBinNode *root) { // Preorder traversal
if (root == NULL) return; // Nothing to visit

if (root->isLeaf()) // Do leaf node
cout << "Leaf: " << ((LeafNode *)root)->value() << endl;

else { // Do internal node

cout << "Internal: "

<< ((IntlNode *)root)->value() << endl;

traverse(((IntlNode *)root)->leftchild());

traverse(((IntlNode *)root)->rightchild());

} }

（2）

#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode {      //Node  base class  基类
public:
    virtual ~VarBinNode(){}
    virtual bool isLeaf() = 0;
    virtual void traverse() = 0;
};

class LeafNode :public VarBinNode {     //Leaf node 叶子结点
private:
    Operand var;        //Operand value 运算数

public:
    LeafNode(const Operand& val) { var = val; }
    bool isLeaf() { return true; }
    Operand value() { return var; } //Return node value
    void traverse() {   //叶子结点的遍历
        cout << "Leaf:" << value() << endl;
    }
};

class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
    VarBinNode* lc;     //Left child 左孩子
    VarBinNode* rc;     //Right child 右孩子
    Operator opx;       //Operator value 运算符号

public:
    IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
        opx = op; lc = l; rc = r;
    }
    bool isLeaf() { return false; }
    VarBinNode* left() { return lc; }   //Return left child左孩子
    VarBinNode* right() { return rc; }  //Return right child右孩子
    Operator value() { return opx; }        //Return operator value 运算符号

    void traverse() {       //非叶子结点的遍历
        cout << "Internal:" << value() << endl;
        if (left() != NULL)left()->traverse();
        if (right() != NULL)right()->traverse();
    }
};

//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
    if (root != NULL)root->traverse();
}

之后再用上面任意一种完成表达式树的构建^3（这里用（2））

#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode {      //Node base class  基类
public:
    virtual ~VarBinNode() {}
    virtual bool isLeaf() = 0;
    virtual void traverse() = 0;
};

class LeafNode :public VarBinNode {     //Leaf node 叶子结点
private:
    Operand var;        //Operand value 运算数

public:
    LeafNode(const Operand& val) { var = val; }
    bool isLeaf() { return true; }
    Operand value() { return var; } //Return node value
    void traverse() {   //叶子结点的遍历
        cout << "Leaf:" << value() << endl;
    }
};

class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
    VarBinNode* lc;     //Left child 左孩子
    VarBinNode* rc;     //Right child 右孩子
    Operator opx;       //Operator value 运算符号

public:
    IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
        opx = op;lc = l; rc = r;
    }
    bool isLeaf() { return false; }
    VarBinNode* left() { return lc; }   //Return left child左孩子
    VarBinNode* right() { return rc; }  //Return right child右孩子
    Operator value() { return opx; }        //Return operator value 运算符号

    void traverse() {       //非叶子结点的遍历
        cout << "Internal:" << value() << endl;
        if (left() != NULL)
        left()->traverse();
        if (right() != NULL)
        right()->traverse();
    }
};

//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
    if (root != NULL)root->traverse();
}

class Expressiontree {      //表达式树
private:
    VarBinNode* Root;       //Tree root 树根
public:
    Expressiontree(Operand op) {        //Leaf constructor 叶子结点的构造函数
        Root = new LeafNode(op);
    }
    //Intlnode constructor  非叶子节点的构造函数
    Expressiontree(const Operator& op, Expressiontree* l, Expressiontree* r) {
        Root = new IntlNode(op, l->Root, r->Root);
    }
    Expressiontree(VarBinNode*& node) {
        Root = node;
    }
    void traversetree() {       //遍历表达式树
        traverse(Root);
    }
    VarBinNode* getRoot() {     //获取树根结点
        return Root;
    }
    ~Expressiontree(){}
};

Expressiontree* buildtree(string s, int l, int r) {     
    //在创建树的时候，如果孩子节点为空，让它指向emptynode节点
    if (r < l)
        return NULL;
    //上面这个判断条件没有必要，因为不会出现这种情况，除非错误输入，比如只输入了: "()"或者"2+"
    int c1 = -1, c2 = -1;
    int flag = 0;
    if (r == l) {           //叶子结点
        return new Expressiontree(s[r]);
    }
    for (int i = l; i <= r; ++i) {
        if (s[i] == '(')
            ++flag;
        else if (s[i] == ')')
            --flag;
        else if (s[i] == '+' || s[i] == '-') {
            if (flag == 0) {        //说明这里的加减号在括号外，可以拿来做根结点
                c1 = i;
            }
        }
        else if (s[i] == '*' || s[i] == '/') {
            if (flag == 0) {
                c2 = i;
            }
        }
    }
    if (c1 < 0)c1 = c2; //如果括号外面没有加减号，用乘除号代替
    if (c1 < 0)return buildtree(s, l + 1, r - 1);
    Expressiontree* left = buildtree(s, l, c1 - 1);
    Expressiontree* right = buildtree(s, c1 + 1, r);
    Expressiontree* op = new Expressiontree(s[c1], left, right);
    return op;
}

void deletetree(IntlNode*tree) {        //删除表达式树，释放空间
    if (tree->left() != NULL) {
        if (tree->left()->isLeaf() == false) {
            deletetree((IntlNode*)tree->left());
        }
        else
            delete tree->left();
    }
    if (tree->right() != NULL) {
        if (tree->right()->isLeaf() == false) {
            deletetree((IntlNode*)tree->right());
        }
        else
            delete tree->right();
    }
    delete tree;
}

int main() {
    string expression = "4*x*(2*x+a)-c";
    //构建表达式树
    Expressiontree* expressiontree = buildtree(expression, 0, expression.size() - 1);
    expressiontree->traversetree();     //遍历表达式树
    deletetree((IntlNode*)expressiontree->getRoot());       //释放空间
}

然后有两个概念需要提及：

  • 前缀表达式
    它将运算符写在前面，操作数写在后面。例如，- 1 + 2 3，它等价于1-(2+3)。

  • 后缀表达式
    和前面相反，操作数在前，运算符在后，
    例如，(2+3)*5,它等价于23+5 *

接着，还是这个图，

1 先序遍历（先根后左再右）就可以得到我们想要的前缀表达式

后序遍历（先左后右再根）就可以得到我们想要的后缀表达式

（2）代码 ：先序遍历结果


2

后序遍历代码：（在（2）基础上加了一个traverse2()方法）

#include<iostream>
using namespace std;
#define Operand char
#define Operator char
//Node implementation with the composite design pattern 复合设计模式
class VarBinNode {      //Node base class  基类
public:
    virtual ~VarBinNode() {}
    virtual bool isLeaf() = 0;
    virtual void traverse() = 0;    //用来先序遍历
    virtual void traverse2() = 0;   //用来后序遍历
};

class LeafNode :public VarBinNode {     //Leaf node 叶子结点
private:
    Operand var;        //Operand value 运算数

public:
    LeafNode(const Operand& val) { var = val; }
    bool isLeaf() { return true; }
    Operand value() { return var; } //Return node value
    void traverse() {   //叶子结点的遍历
        cout << "Leaf:" << value() << endl;
    }
    void traverse2() {  //叶子结点的遍历
        cout << "Leaf:" << value() << endl;
    }
};

class IntlNode :public VarBinNode { //Internal node 非叶子节点
private:
    VarBinNode* lc;     //Left child 左孩子
    VarBinNode* rc;     //Right child 右孩子
    Operator opx;       //Operator value 运算符号

public:
    IntlNode(const Operator& op, VarBinNode* l, VarBinNode* r) {
        opx = op;lc = l; rc = r;
    }
    bool isLeaf() { return false; }
    VarBinNode* left() { return lc; }   //Return left child左孩子
    VarBinNode* right() { return rc; }  //Return right child右孩子
    Operator value() { return opx; }        //Return operator value 运算符号

    void traverse() {       //非叶子结点的遍历
        cout << "Internal:" << value() << endl;
        if (left() != NULL)
        left()->traverse();
        if (right() != NULL)
        right()->traverse();
    }
    void traverse2() {      //非叶子结点的遍历
        if (left() != NULL)left()->traverse2();
        if (right() != NULL)right()->traverse2();
        cout << "Internal:" << value() << endl;
    }
};

//Do a preorder traversal先序遍历
void traverse(VarBinNode* root) {
    if (root != NULL)root->traverse();
}
//Do a postorder traversal后序遍历
void traverse2(VarBinNode* root) {
    if (root != NULL)root->traverse2();
}

class Expressiontree {      //表达式树
private:
    VarBinNode* Root;       //Tree root 树根
public:
    Expressiontree(Operand op) {        //Leaf constructor 叶子结点的构造函数
        Root = new LeafNode(op);
    }
    //Intlnode constructor  非叶子节点的构造函数
    Expressiontree(const Operator& op, Expressiontree* l, Expressiontree* r) {
        Root = new IntlNode(op, l->Root, r->Root);
    }
    Expressiontree(VarBinNode*& node) {
        Root = node;
    }
    void traversetree() {       //遍历表达式树，先序
        traverse(Root);
    }
    void traversetree2() {      //遍历表达式树，后序
        traverse2(Root);
    }
    VarBinNode* getRoot() {     //获取树根结点
        return Root;
    }
    ~Expressiontree(){}
};

Expressiontree* buildtree(string s, int l, int r) {     
    //在创建树的时候，如果孩子节点为空，让它指向emptynode节点
    if (r < l)
        return NULL;
    //上面这个判断条件没有必要，因为不会出现这种情况，除非错误输入，比如只输入了: "()"或者"2+"
    int c1 = -1, c2 = -1;
    int flag = 0;
    if (r == l) {           //叶子结点
        return new Expressiontree(s[r]);
    }
    for (int i = l; i <= r; ++i) {
        if (s[i] == '(')
            ++flag;
        else if (s[i] == ')')
            --flag;
        else if (s[i] == '+' || s[i] == '-') {
            if (flag == 0) {        //说明这里的加减号在括号外，可以拿来做根结点
                c1 = i;
            }
        }
        else if (s[i] == '*' || s[i] == '/') {
            if (flag == 0) {
                c2 = i;
            }
        }
    }
    if (c1 < 0)c1 = c2; //如果括号外面没有加减号，用乘除号代替
    if (c1 < 0)return buildtree(s, l + 1, r - 1);
    Expressiontree* left = buildtree(s, l, c1 - 1);
    Expressiontree* right = buildtree(s, c1 + 1, r);
    Expressiontree* op = new Expressiontree(s[c1], left, right);
    return op;
}

void deletetree(IntlNode*tree) {        //删除表达式树，释放空间
    if (tree->left() != NULL) {
        if (tree->left()->isLeaf() == false) {
            deletetree((IntlNode*)tree->left());
        }
        else
            delete tree->left();
    }
    if (tree->right() != NULL) {
        if (tree->right()->isLeaf() == false) {
            deletetree((IntlNode*)tree->right());
        }
        else
            delete tree->right();
    }
    delete tree;
}

int main() {
    string expression = "4*x*(2*x+a)-c";
    //构建表达式树
    Expressiontree* expressiontree = buildtree(expression, 0, expression.size() - 1);
    expressiontree->traversetree2();        //遍历表达式树
    deletetree((IntlNode*)expressiontree->getRoot());       //释放空间
}

后序遍历结果：


3

---------------------------

表达式树优化

代码优化：
在非叶节点traverse()方法中，我们看到每次递归遍历前，都要判断左右子节点是否为空，当树的深度增加时，这造成的时间开销是呈指数增长的，因此我们最好把这两个判断条件给去掉。

（不过因为这里情况特殊，即我们的表达式树一定是一个满二叉树（二元运算符肯定对应了两个操作数），所以可以大胆地去掉判断条件，不过这样还是不好，如果我们的输入出现差错，就有可能导致程序崩溃，因为使用了空指针）

优化实现

Reference

^1《数据结构与算法分析（C++版）（第三版）》P103

^2《数据结构与算法分析（C++版）（第三版）》P104,P105

^3表达式树与前中后缀表达式

相关文章

  • 二叉树的应用----表达式树

    文章目录 何为表达式树 表达式树实现 作为二叉树的一个应用，这里就用二叉树这种数据结构来实现~ 这里有一个重要的知...

  • 数据结构（C++实现）--二叉树

    二叉树 二叉树是每个父节点最多只有两个子节点 如图，是表达式的二叉树的表示。引申出： 满二叉树，每个父节点都有两个...

  • 二叉树的前序中序和后续遍历及应用场景

    二叉树遍历的应用： （1）前序遍历：可以用来实现目录结构的显示。 （2）中序遍历：可以用来做表达式树，在编译器底层...

  • 【Python】（十七）Python实现树结构

    本节我们将用Python实现树结构中最简单的二叉树，并将在以后的章节中应用它。 二叉树类 二叉树的遍历

  • 运用

    递归应用，计算二叉树的深度和二叉树的高度。自顶向下和自顶向上的思路

  • 精选-LC

    10. 正则表达式匹配 617. 合并二叉树 104. 二叉树的最大深度 557. 反转字符串中的单词 III 5...

  • day04-栈

    栈 解决实际问题： 表达式的求职和转换（中缀表达式转后缀表达式） 二叉树的遍历 深度优先搜索 概念： 栈（stac...

  • 算法与数据结构系列之[最大堆-上]

    前面三篇我们介绍了二叉树以及二叉树的代码实现，这篇介绍一下堆这种数据结构，是对二叉树的一个应用，堆其实是用二叉树实...

  • 3.有关二叉树的算法

    1.分层遍历二叉树：宽度优先遍历 2.分层遍历应用，按层打印二叉树 3.前序遍历二叉树 4.前序遍历，迭代 5.中...

  • C语言实现二叉树的各种遍历及求解深度

    一、介绍 二叉树是一种重要的数据结构，在很多方面都有重要的应用，此文主要记录了二叉树的基础知识，包括二叉树的建立、...

网友评论

      本文标题：二叉树的应用----表达式树

      本文链接：https://www.haomeiwen.com/subject/fhkvoctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|二叉树的应用----表达式树|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！