【数据结构 | C语言】后缀式建二叉树

【数据结构 | C语言】后缀式建二叉树

原创代码，如有错误，欢迎指正。

阅读建议：Tree.c部分提供了基本函数，由于不是本文主要内容，因此将其单独放在一个文件里面。读者可以跳过此部分，当不理解某个函数时，再回到Tree.c查阅即可

后缀式建二叉树规则：

        遍历后缀式，如果是 *** 作数，直接入栈。如果是运算，出栈两个 *** 作数结合生成小树，并将其入栈。后缀式建树相较中缀式简单

postExpTree.c：

post：后        Exp：表达式        Tree：树

# include "Tree.c"

pnode postExpTree(char cc[]) {
    // 建表达式栈
    pstack pexp = CreateStack();
    char c;
    for (int i=0; idata = c;
        if (!(c>='a' && c<='z')) {    // 此步是关键，如果当前字符是操作符，出栈生成小树，再入栈。否则直接入栈
            new->rnode = pop(pexp);
            new->lnode = pop(pexp);
        }
        push(pexp, new);
    }
    if (1 == pexp->now) {
        printf("OKn");
    } else {
        printf("剩余：%d个n", pexp->now);
    }
    return pop(pexp);
}

int main() {
    char cc[MAX_SIZE] = "ace/-g+";
    pnode root = postExpTree(cc);

    // 输出
    printf("preOrder : ");
    preOrder(root);
    printf("ninOrder : ");
    inOrder(root);
    printf("npostOrder : ");
    postOrder(root);
    
    return 0;
}

Tree.c：

# include 
# include 
# include 

# define ElemType char
# define MAX_SIZE 20
# define true 1
# define false 0

typedef int bool;
typedef struct Tree node;
typedef struct Tree *pnode;
typedef struct Stack stack;
typedef struct Stack *pstack;

// stack
struct Stack {
    pnode *list;
    int size;
    int now;
};

// tree
struct Tree {
    ElemType data;
    struct Tree *lnode, *rnode;
};

// tree
pnode CreateNode();
void AddNode(pnode *root, ElemType data);
void preOrder(pnode root);
void inOrder(pnode root);
void postOrder(pnode root);
// stack
pstack CreateStack();
bool empty(pstack ps);
bool full(pstack ps);
void append(pstack ps);
void push(pstack ps, pnode new);
pnode pop(pstack ps);
pnode peek(pstack ps);


pnode CreateNode() {
    pnode pnew = (pnode) malloc(sizeof(node));
    memset(pnew, 0, sizeof(node));
    return pnew;
}

void AddNode(pnode *root, ElemType data) {
    pnode pnew = CreateNode();
    pnew->data = data;
    *root = pnew;
}

void preOrder(pnode root) {
    if (root) {
        printf("%ct", root->data);
        preOrder(root->lnode);
        preOrder(root->rnode);
    }
}

void inOrder(pnode root) {
    if (root) {
        inOrder(root->lnode);
        printf("%ct", root->data);
        inOrder(root->rnode);
    }
}

void postOrder(pnode root) {
    if (root) {
        postOrder(root->lnode);
        postOrder(root->rnode);
        printf("%ct", root->data);
    }
}

pstack CreateStack() {
    pstack ps = (pstack) malloc(sizeof(stack));
    ps->now = 0;
    ps->size = MAX_SIZE;
    ps->list = (pnode*) malloc(sizeof(pnode)*ps->size);
    return ps;
}

bool empty(pstack ps) {
    if (0 == ps->now) {
        return true;
    } else {
        return false;
    }
}

bool full(pstack ps) {
    if (ps->size == ps->now) {
        return true;
    } else {
        return false;
    }
}

void append(pstack ps) {
    ps->size += 10;
    pnode *new = (pnode*) malloc(sizeof(pnode)*ps->size);
    for (int i=0; inow; i++) {
        new[i] = ps->list[i];
    }
    free(ps->list);
    ps->list = new;
}

void push(pstack ps, pnode new) {
    if (full(ps)) {
        append(ps);
    }
    ps->list[ps->now++] = new;
}

pnode pop(pstack ps) {
    if (empty(ps)) {
        return NULL;
    } else {
        return ps->list[--ps->now];
    }
}

pnode peek(pstack ps) {
    if (empty(ps)) {
        return NULL;
    } else {
        return ps->list[ps->now-1];
    }
}