注册 登录
编程论坛 数据结构与算法

二叉树求表达式,请教!

wcmk21 发布于 2014-05-13 17:28, 605 次点击
最近碰到二叉树求表达式的问题,一直想不明白,请高手指点!
————————————————————————————————————————————————————————————————————————————
1.利用二叉树求表达式,不利用栈可以吗?
    利用栈的话,可以在输入的时候直接判断操作数和操作符并分别压入操作数栈和操作符栈;现在想利用二叉树直接求值,感觉此时再借助栈的话,二叉树就变得多余了。我查了一些前辈的代码,好多都要借助栈;现在,我想只用二叉树,真的可以吗?
2.我希望可以输入原始的表达式,而不是转换成后缀式等,并根据输入的字符动态建立二叉树
    例如,输入:2.2*(3.1+1.20)-7.5/3
          输出:6.96
————————————————————————————————————————————————————————————————————————————
本想建立二叉树,例如a+b*c-d;
建立后:
                      -
                    /    \
                   /       \
                  +         d
                 / \   
                /   \
               a     *
                    / \
                   /   \
                  b     c
我想到的是将优先极高的操作符存于比其低的结点的右子树上,可是当我把“a+b*c”存好后,不知道怎么将“—”存在“+”的上一结点。请高手教教我,谢谢了!
3 回复
#2
azzbcc2014-05-13 21:38
struct S
{
  int   flag;    // flag 可取 {0, 1}, 0 表示 当前结点 数值有效,1 表示当前结点 运算符有效
  union U
  {
    int   num;     // 数值
    char  operator;//运算符
  }data;
  struct S *lchild;
  struct S *rchild;
}
#3
wcmk212014-05-14 13:27
回复 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;
}
感觉最后,可能会出现有块内存不会被使用的情况。
完整的程序已经写好了,测试了几组数据还好。
谢谢回复。
#4
wcmk212014-05-14 13:28
回复 3 楼 wcmk21
总是感觉不太合理,但是,能出来结果,我真的感觉很高兴,前几天搞得我头昏脑涨的
1