交换二叉树的左右子树——非递归方式_非递归实现二叉树左右子树交换

#include <stdio.h>
#include <stdlib.h>
 
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