a
/
b c
/ /
d * * e
*/
//先序序列为abdce,输入为abd***c*e**(*表示空格,代表空树),输入按满二叉树输入
//每一个节点都是一个子树的根节点
void pre_create_tree(treenode **T){ //递归法 char datatemp; fflush(stdin); datatemp=getchar(); if(datatemp=='*'){ *T=NULL; } else{ if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){ exit(0); } else{ (*T)->data=datatemp; (*T)->lc = (*T)->rc = NULL; pre_create_tree(&(*T)->lc); pre_create_tree(&(*T)->rc); } } } void pre_visit_tree(treenode *T){ //递归法 if(T!=NULL){ printf("%c ", T->data); pre_visit_tree(T->lc); pre_visit_tree(T->rc); } else{ return; } } struct stack_typedef{ treenode** stack_head; treenode** stack_top; int stack_used; }; typedef struct stack_typedef stack; #define stack_max 1000 void stack_init(stack *mystack){ if((mystack->stack_head=(treenode**)malloc(sizeof(treenode*)*stack_max))==NULL) exit(0); mystack->stack_used = 0; mystack->stack_top = mystack->stack_head; } void stack_del(stack *mystack){ free(mystack->stack_head); } void stack_push(stack *mystack, treenode *data){ if(mystack->stack_used<stack_max){ *(mystack->stack_top) = data; mystack->stack_used ++; mystack->stack_top ++; } } treenode* stack_pop(stack *mystack){ if(mystack->stack_used>0){ mystack->stack_used--; mystack->stack_top--; return *mystack->stack_top; } return NULL; } void pre_visit_tree2(treenode *T){ //非递归法,需要使用栈保证输出正确,递归<=>栈 stack mystack; stack_init(&mystack); while(1){ printf("%c ", T->data); if(T->lc!=NULL){ stack_push(&mystack, T); T=T->lc; } else if(T->rc!=NULL){ //stack_push(&mystack, T); T=T->rc; } else{ //T=stack_pop(&mystack); while(T->rc==NULL&&mystack.stack_used!=0){ T=stack_pop(&mystack); } if(T->rc!=NULL) T=T->rc; else break; } }; printf(" "); }