由后序遍历可知，输入顺序是左结点->右结点->子树根结点
比如输入如下树：
a
/ \
b c
/
d
\
e
输入序列为 * * * e d * b * * c a $
思路：
使用栈，对左结点和右结点进行压栈；
1.当输入遇到非*，且栈中元素大于等于2，则可以确定一个小三角树形，并将这个树根作为下一个小三角树形的一个子节点；
2.当输入遇到非*，但栈中元素小于2，则直接将此元素压入栈中；
3.当输入遇到*，压入NULL；
4.当输入遇到$，输入结束。
#include#include #include typedef struct node{ struct node* lc; struct node* rc; int id;}node;typedef struct stack{ node **head; node **top; int max; int used;}stack;#define stack_increasement 20#define stack_initsize 10void init_stack(stack *s){ s->used = 0; s->head = (node**)malloc(sizeof(node*)*stack_initsize); s->top = s->head; s->max = stack_initsize;}void push_stack(stack *s, node* d){ *(s->top++) = d; s->used ++; if(s->used==s->max){ s->max+=stack_increasement; s->head = (node**)realloc(s->head, sizeof(node*)*s->max); s->top = s->head+s->used; }}node* pop_stack(stack *s){ if(s->used==0) return (node*)-1; s->used --; s->top --; return *(s->top);}void bc(node **T){ int input; stack s; node *lctmp, *rctmp; node *temp; init_stack(&s); scanf("%d", &input); while(input!=0){ if(input<0){ push_stack(&s, NULL); } else{ if(s.used>=2){ rctmp = pop_stack(&s); lctmp = pop_stack(&s); temp = (node*)malloc(sizeof(node)); temp->lc = lctmp; temp->rc = rctmp; temp->id = input; push_stack(&s, temp); } else{ temp = (node*)malloc(sizeof(node)); temp->lc = NULL; temp->rc = NULL; temp->id = input; push_stack(&s, temp); } } scanf("%d", &input); } *T = pop_stack(&s);}void pre_visit_tree(node *T){ //递归法 if(T!=NULL){ printf("%d ", T->id); pre_visit_tree(T->lc); pre_visit_tree(T->rc); } else{ return; }}int main(void){ node *tree; bc(&tree); pre_visit_tree(tree); system("pause"); return 0;}