題目

設(shè)計算法，將給定表達(dá)式樹轉(zhuǎn)換為等價的中綴表達(dá)式（通過括號反映操作符的計算次序）并輸出。

思想

中序遞歸遍歷，當(dāng)遍歷到是操作符的非頭結(jié)點時，在開頭加左括號，結(jié)尾加右括號。

代碼

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);
}

運行結(jié)果

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;
}