2017-408算法题

题目

设计算法，将给定表达式树转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。

思想

中序递归遍历，当遍历到是操作符的非头结点时，在开头加左括号，结尾加右括号。

代码

void midSubTree(BTree T) {
    if (T->left != NULL || T->right != NULL) {
        printf("( ");
        if (T->left != NULL) 
            midSubTree(T->left);
        printf("%c ", T->data);
        if (T->right != NULL) 
            midSubTree(T->right);
        printf(") ");
    }
    else 
        printf("%c ", T->data);
}

void midTree(BTree T) {
    if (T->left!=NULL) 
        midSubTree(T->left);
    printf("%c ", T->data);
    if (T->right != NULL)
        midSubTree(T->right);
}

运行结果

int main() {
    BTree root;
    creatNode(root, '*');

    BTNode *l;
    creatNode(l, '+');
    BTNode *l1;
    creatNode(l1, 'a');
    BTNode *l2;
    creatNode(l2, 'b');
    l->left = l1;
    l->right = l2;

    BTNode *r;
    creatNode(r, '*');
    BTNode *r1;
    creatNode(r1, 'c');
    BTNode *r2;
    creatNode(r2, '-');
    BTNode *r3;
    creatNode(r3, 'd');
    r2->right = r3;
    r->left = r1;
    r->right = r2;

    root->left = l;
    root->right = r; 
    midTree(root);
    return 0;
}

捕获4.PNG

其他代码

#include<stdio.h>
#include<stdlib.h>

typedef struct node {
    struct node *left;
    struct node *right;
    char data;
}BTNode, *BTree;

void creatNode(BTree &T, char ch) {
    T = (BTNode*)malloc(sizeof(BTNode));
    T->data = ch;
    T->left = NULL;
    T->right = NULL;
}