//用输入的前缀表达式建立二叉树
BinaryTreeNode* PrefixToBinaryree(char a[])
{
    using std::stack;
stack<BinaryTreeNode* >aStack;
int i=0;//设置I来记录A串的当前值下标
BinaryTreeNode* pointer;//记录新建立的二叉树当前结点的指针
BinaryTreeNode* root;//记录根结点的指针
BinaryTreeNode* prev;//记录栈顶指针
root=pointer=new BinaryTreeNode(a[i]);
if(a[i]!='+'&&a[i]!='-'&&a[i]!='*'&&a[i]!='/'){//根结点不是操作符
cout<<"输入错误"<<endl;//提示出错信息
return NULL;
}
aStack.push(pointer);
i++;
while(a[i]!='\0'){
pointer=new BinaryTreeNode(a[i]);//以A[]为内容建立新的结点
if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/'){
    if(aStack.empty()){
aStack.push(pointer);//若栈为空直接压栈
i++;
}
    else{
pre=aStack.top();
if(pre->left==NULL){
pre->left=pointer;//若栈顶指针所指接点左孩子为空社当前接点为其左孩子
aStack.push(pointer);//当前指针进栈
i++;}
else if(pre->right!=NULL){
cout<<"输入错误"<<endl;
return NULL;
}else{
    pre->right=pointer;
    aStack.pop();//栈顶指针左右孩子设置完毕把他弹出
    aStack.push(pointer);
    i++;
}
}
}else{
    if(aStack.empty()){
cout<<"输入错误"<<endl;
return NULL;
}
    else{
pre=aStack.top();
if(pre->left==NULL){
pre->left=pointer;
aStack.push(pointer);
i++;
}else if(pre->left!=NULL){
cout<<"输入错误"<<endl;
return NULL;
}else{
    pre->right=pointer;
    aStack.pop();
    i++;
}
}
}
}
return root;
}

//实现中缀表达式转化为后缀表达式
void ConvertIfixToPostfix(char a[],char b[])
{
    using std::stack;
    stack<char>aStack;
    int i=0,j=0;
    while(a[i]!='\0')
    {
        if(=='+'||a[i]=='-')
        {
            while(!aStack.empty()&&aStack.top()!='(')
            {
                b[j]=aStack.top();
                aStack.top();
                j++;
            }
            aStack.push(a[i]);
            i++;
        }
        else if(a[i]=='*'||a[i]=='/')
        {
            while(!aStack.empty()&&aStack.top()!='('&&a[i]!='+'&&a[i]!='-')
                b[j]=aStack.top();
            aStack.top();
            j++;
        }
        aStack.push(a[i]);
        i++;
    }
    else if(a[i]=='(')
    {
        aStack.push(a[i]);
        i++;
    }
    else if(a[i]==')')
    {
        if(aStack.empty())
            cout<<"输入错误"<<endl;
        return ;
    }
    else
    {
        while(!aStack.empty()&&aStack.top()!='(')
        {
            b[j]=aStack.top();
            aStack.top();
            j++;
        }
        if(aStack.empty())
        {
            cout<<"输入错误"<<endl;
            return ;
        }else aStack.pop();
    }
    i++;
}
else
{
    b[j]=a[i];
    j++;i++;
}
}
while(!aStack.empty())
{
    if(aStack.top()=='(')
    {
        cout<<"输入错误"<<endl;
        return ;
    }else{
        b[j]=aStack.top();
        aStack.top();
        j++;
    }
}
b[j]='\0';
}
//输出中缀表达式
void Infixprint(BinaryTreeNode* root)
{
    if(root!=NULL){
        switch(root->value()){
        case '+':
        case '-':
    Infixprint(root->leftchild());
    cout<<root->value();
        Infixprint(root->rightchild());
    break;
        case '*':
        case '/':
    parentnode=root;
    root=parentnode->leftchild();
    if(root->value()=='-'||root->value()=='+'){
    cout<<"(";
    Infixprint(root->leftchild());
        cout<<")";
    }else Infixprint(root->leftchild());
    cout<<parentnode->value();
    root=parentnode->rightchild();
    if(root->value()=='-'||root->value()=='+'){
    cout<<"(";
    Infixprint(root->rightchild());
        cout<<")";
    }else Infixprint(root->rightchild());
break;
        default: cout<<root->value();
}
}
}