#include#include struct node{ char data ; struct node* left ; struct node* right ; }; struct tree{ struct node* root ; }; void tree_create( struct node** node){ char data; scanf("%c" , &data); if(data == '#' ){ *node = NULL; } else{ *node = ( struct node*)malloc(sizeof( struct node)); (*node)-> data = data; tree_create(&(*node)-> left); tree_create(&(*node)-> right); } } void tree_destory( struct node** node){ if(*node != NULL){ tree_destory(&(*node)-> left); tree_destory(&(*node)-> right); free(node); } } void tree_first( struct node* node){ if(node == NULL) return; printf("%c " , node->data); tree_first(node-> left); tree_first(node-> right); } static struct node* stack[5] = {0}; static int pos = -1; void push( struct node* node){ stack[++pos] = node; } void pop(){ --pos; } int empty(){ return pos == -1; } struct node* top(){ return stack[pos]; } void exchange( struct node* node){ struct node* tnode = node; struct node* tmp = NULL; if(node == NULL) return; while(1){ tmp = tnode-> left; tnode-> left = tnode->right ; tnode-> right = tmp; if(tnode->right ){ push(tnode-> right); } if(tnode->left ){ tnode = tnode->left; } else{ if(!empty()){ tnode = top(); pop(); } else{ break; } } } } int main(){ struct tree tree; tree_create(&tree. root); printf("交换前的先序遍历：" ); tree_first(tree. root); printf("\n" ); exchange(tree. root); printf("交换后的先序遍历：" ); tree_first(tree. root); printf("\n" ); tree_destory(&tree. root); return 0; }
本文链接：http://blog.csdn.net/girlkoo/article/details/17605349
本文作者：girlkoo