表达式转二叉树并三种模式输出

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100
//将中缀表达式转换为前缀表达式。
typedef struct Node
{
    char key;
    struct Node * left;
    struct Node * right;
}Node;
//search for the operator with the highest grade in a
int search(char a[], int begin, int end)
{
    int tag = -1;
    int isInBrackets = 0;//是否在括号里面
    if(a[begin] == '(' && a[end] == ')')
    {
        begin += 1;
        end -= 1;
    }
    int amExist = 0;//是否存在。
    for(int i = begin; i < end; i++)
    {
        if(a[i] == '(')
            isInBrackets++;
        if(a[i] == ')')
            isInBrackets--;
        if((a[i] == '+' || a[i] == '-') && isInBrackets == 0)
        {
            tag = i;
            amExist = 1;
        }
        if((a[i] == '*' || a[i] == '/') && isInBrackets == 0 && amExist == 0)
        {
            tag = i;
        }
    }
    return tag;
}
//build the binary tree
Node * buildBinaryTree(char a[], int begin, int end)
{
    Node * p = NULL;
    if(begin == end)
    {
        p = (Node *)malloc(sizeof(Node));
        p->key = a[begin];
        p->left = NULL;
        p->right = NULL;
    }
    else
    {
        int tag;
        tag = search(a,begin,end);
        if (tag<0) {
            printf("对不起，请输入正确的表达式。");
            return NULL;//tag小于0的时候不是表达式。
        }
        p = (Node *)malloc(sizeof(Node));
        p->key = a[tag];
        if(a[begin] == '(' && a[end] == ')')
        {
            begin += 1;
            end -= 1;
        }
        p->left = buildBinaryTree(a, begin, tag - 1);
        p->right = buildBinaryTree(a, tag + 1, end);
    }
    return p;
}
void outputBinaryTree_pre(Node * head)
{
    if(head)
    {
        printf("%c", head->key);
        outputBinaryTree_pre(head->left);
        outputBinaryTree_pre(head->right);
    }
}
void outputBinaryTree_in(Node * head)
{
    if(head)
    {
       
        outputBinaryTree_in(head->left);
        printf("%c", head->key);
        outputBinaryTree_in(head->right);
    }
}
void outputBinaryTree_post(Node * head)
{
    if(head)
    {
       
        outputBinaryTree_post(head->left);
        outputBinaryTree_post(head->right);
        printf("%c", head->key);
    }
}

int main()
{
    printf("please input a expression:");
    char input[N];
    while(scanf("%s", input))
    {
        if(strcmp(input, "exit") == 0)
        {
            break;
        }
        Node * head = NULL;
        int length = (int)strlen(input);
        head = buildBinaryTree(input, 0, length - 1);
        printf("前缀输出为：\n");
        outputBinaryTree_pre(head);//这个必须放在在里面，因为他是一个个输出的。
        printf("\n中缀输出为：\n");
        outputBinaryTree_in(head);//这个必须放在在里面，因为他是一个个输出的。
        printf("\n后缀输出为：\n");
        outputBinaryTree_post(head);//这个必须放在在里面，因为他是一个个输出的。
        printf("\n");
    }
   
   
   
   
    return 0;
}

原文地址：http://www.software8.co/wzjs/cpp/2929