題目來源：
http://blog.163.com/prevBlogPerma.do?host=zhedahht&srl=2541117420072159363370&mode=prev題目：輸入一顆二元查找樹，將該樹轉(zhuǎn)換為它的鏡像，即在轉(zhuǎn)換后的二元查找樹中，左子樹的結(jié)點都大于右子樹的結(jié)點。用遞歸和循環(huán)兩種方法完成樹的鏡像轉(zhuǎn)換。
例如輸入：
8
/ \
6 10
/\ /\
5 7 9 11
輸出：
8
/ \
10 6
/\ /\
11 9 7 5
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct Node {
int value;
struct Node *left;
struct Node *right;
};
void
bst_preorder(struct Node *root)
{
if(root == NULL)
return;
printf("%d\t", root->value);
bst_preorder(root->left);
bst_preorder(root->right);
}
void
bst_mirror_recursive(struct Node *root) /* easy */
{
if(root == NULL)
return;
struct Node *ptr = root->left;
root->left = root->right;
root->right = ptr;
bst_mirror_recursive(root->left);
bst_mirror_recursive(root->right);
}
/* STACK : naive */
#define STACK_SIZE 101
struct Stack {
void *data[STACK_SIZE];
int top;
};
void
stack_pop(struct Stack *stack)
{
if((stack->top) >= 0)
--(stack->top);
}
void *
stack_top(struct Stack *stack)
{
if((stack->top) >= 0)
return stack->data[stack->top];
return NULL;
}
void
stack_push(struct Stack *stack, void *entity)
{
stack->data[++(stack->top)] = entity;
}
int
stack_isempty(struct Stack *stack)
{
return (stack->top) < 0;
}
void
bst_mirror_nonrecursive(struct Node *root, struct Stack *aux_stack) /* stack used : good method */
{
stack_push(aux_stack, root);
while(!stack_isempty(aux_stack)) {
struct Node *node = (struct Node *)stack_top(aux_stack);
struct Node *ptr = node->left;
node->left = node->right;
node->right = ptr;
stack_pop(aux_stack);
if(node->left)
stack_push(aux_stack, node->left);
if(node->right)
stack_push(aux_stack, node->right);
}
}
int
main(int argc, char **argv)
{
struct Node a = {5, NULL, NULL};
struct Node b = {7, NULL, NULL};
struct Node c = {9, NULL, NULL};
struct Node d = {11, NULL, NULL};
struct Node e = {6, &a, &b};
struct Node f = {10, &c, &d};
struct Node g = {8, &e, &f};
bst_preorder(&g);
printf("\n");
bst_mirror_recursive(&g);
bst_preorder(&g);
printf("\n");
bst_mirror_recursive(&g);
bst_preorder(&g);
printf("\n");
struct Stack aux = {{0}, -1};
bst_mirror_nonrecursive(&g, &aux);
bst_preorder(&g);
printf("\n");
return 0;
}