| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 605 人关注过本帖
标题:二叉树求表达式,请教!
只看楼主 加入收藏
wcmk21
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2013-3-17
结帖率:100%
收藏
已结贴  问题点数:10 回复次数:3 
二叉树求表达式,请教!
最近碰到二叉树求表达式的问题,一直想不明白,请高手指点!
————————————————————————————————————————————————————————————————————————————
1.利用二叉树求表达式,不利用栈可以吗?
    利用栈的话,可以在输入的时候直接判断操作数和操作符并分别压入操作数栈和操作符栈;现在想利用二叉树直接求值,感觉此时再借助栈的话,二叉树就变得多余了。我查了一些前辈的代码,好多都要借助栈;现在,我想只用二叉树,真的可以吗?
2.我希望可以输入原始的表达式,而不是转换成后缀式等,并根据输入的字符动态建立二叉树
    例如,输入:2.2*(3.1+1.20)-7.5/3
          输出:6.96
————————————————————————————————————————————————————————————————————————————
本想建立二叉树,例如a+b*c-d;
建立后:
                      -
                    /    \
                   /       \
                  +         d
                 / \   
                /   \
               a     *
                    / \
                   /   \
                  b     c
我想到的是将优先极高的操作符存于比其低的结点的右子树上,可是当我把“a+b*c”存好后,不知道怎么将“—”存在“+”的上一结点。请高手教教我,谢谢了!
搜索更多相关主题的帖子: 表达式 二叉树 
2014-05-13 17:28
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:江西财经大学
等 级:贵宾
威 望:81
帖 子:3293
专家分:12919
注 册:2012-11-4
收藏
得分:10 
struct S
{
  int   flag;    // flag 可取 {0, 1}, 0 表示 当前结点 数值有效,1 表示当前结点 运算符有效
  union U
  {
    int   num;     // 数值
    char  operator;//运算符
  }data;
  struct S *lchild;
  struct S *rchild;
}


[fly]存在即是合理[/fly]
2014-05-13 21:38
wcmk21
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2013-3-17
收藏
得分:0 
回复 2 楼 azzbcc
谢谢,版主。
但是昨天奋斗到现在我终于解决了。
我使用的是操作符和操作数同为double,期间强制转换成char。
下面是我的建立代码,还是感觉有个小问题:
void CreateBitree(BiTree &tree)
{
    char ch;double num;
    tree =new BiTNode;
    BiTree p,q,root=tree;
    //p当前结点
    p=root;
    cin.get(ch);
    //丢弃左括号
    while(ch=='(')
        cin.get(ch);
    if(isdigit(ch))
    {
        get_data(ch,num);
        q=new BiTNode;
        q->data=num;
        q->lchild=NULL;
        q->hchild=NULL;
        p->lchild=q;
    }
    while(ch!='\n')
    {
        p->data=ch;
        cin.get(ch);
        if(isdigit(ch))
            get_data(ch,num);
    //操作符比当前结点的操作符优先级高
    if(compare((char)p->data,ch)=='>')
    {
        //丢弃左括号
        if(ch=='(')
        {
            while(ch=='(')
            cin.get(ch);
            get_data(ch,num);
        }
        q=new BiTNode;
        p->hchild=q;
        p=q;
        p->lchild=new BiTNode;
        p->lchild->data=num;
        p->lchild->lchild=NULL;
        p->lchild->hchild=NULL;
    }
    //操作符比当前结点的操作符优先级低
    else if(compare((char)p->data,ch)=='<')
    {
        //丢弃右括号
        while(ch==')')
            cin.get(ch);
        p->hchild=new BiTNode;
        p->hchild->data=num;
        p->hchild->lchild=NULL;
        p->hchild->hchild=NULL;
        if(ch=='\n') break;
        q=new BiTNode;
        q->lchild=root;
        p=root=q;
    }
    }//while
    p->hchild=new BiTNode;
    p->hchild->data=num;
    p->hchild->lchild=NULL;
    p->hchild->hchild=NULL;
    tree=root;
}
感觉最后,可能会出现有块内存不会被使用的情况。
完整的程序已经写好了,测试了几组数据还好。
谢谢回复。
2014-05-14 13:27
wcmk21
Rank: 1
等 级:新手上路
帖 子:14
专家分:0
注 册:2013-3-17
收藏
得分:0 
回复 3 楼 wcmk21
总是感觉不太合理,但是,能出来结果,我真的感觉很高兴,前几天搞得我头昏脑涨的
2014-05-14 13:28
快速回复:二叉树求表达式,请教!
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.046543 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved