题目： 输入1个二叉查找树，将该树转换为它的镜像，即在转换后的二叉查找树中，左子树的节点都大于右子树的节点，用递归和循环两种方法完成。
二叉查找树中序遍历是从小到大的，镜像树是从大到小的，可用来判断是否转换成功
代码，递归的:
/* 二叉查找树转换前中序遍历是从小到大，转换后是从大到小 递归: 若节点有左孩子或者右孩子的话，首先转换左子树，再转换右子树，然后交换节点左右孩子 */ #include<iostream> using namespace std; typedef int datatype; typedef struct node { datatype value; struct node* lchild; struct node* rchild; }Tree; //先序建树，NULL节点用0表示 Tree* create_tree(void) { int value; Tree* t=NULL; cin>>value; if(value==0) return NULL; else { t=new Tree; t->value=value; t->lchild=create_tree(); t->rchild=create_tree(); } return t; } //释放 void free_tree(Tree* t) { if(t) { free_tree(t->lchild); free_tree(t->rchild); delete t; t=NULL; } } Tree* temp=NULL; void converse(Tree* t) { if(t->lchild || t->rchild) { converse(t->lchild); converse(t->rchild); temp=t->lchild; t->lchild=t->rchild; t->rchild=temp; } } void inorder(Tree* t) { if(t) { inorder(t->lchild); cout<<t->value<<" "; inorder(t->rchild); } } int main(void) { Tree* root; root=create_tree(); cout<<"before..."<<endl; inorder(root); cout<<endl; cout<<"after..."<<endl; converse(root); inorder(root); cout<<endl; free_tree(root); }
代码，循环的:
/* 循环: 应该采用后续遍历，先处理子女，再处理自己 */ #include<iostream> using namespace std; typedef struct node { int value; struct node* lchild; struct node* rchild; }Tree; typedef struct { Tree* p; int count; }Node; //栈 #define MAX 100 typedef struct { Node data[MAX]; int top; }Stack; Stack* create_stack(void) { Stack* s=new Stack; if(s) s->top=-1; return s; } bool empty_stack(Stack* s) { if(s->top==-1) return true; return false; } bool full_stack(Stack* s) { if(s->top==MAX-1) return true; return false; } void push_stack(Stack* s,Node x) { if(full_stack(s)) return ; ++s->top; (s->data[s->top]).p=x.p; (s->data[s->top]).count=x.count; } void pop_stack(Stack* s,Node* x) { if(empty_stack(s)) return ; x->p=(s->data[s->top]).p; x->count=(s->data[s->top]).count; --s->top; } //先序建树 Tree* create_tree(void) { int value; Tree* t=NULL; cin>>value; if(0==value) return NULL; else { t=new Tree; t->value=value; t->lchild=create_tree(); t->rchild=create_tree(); } return t; } void free_tree(Tree* t) { if(t) { free_tree(t->lchild); free_tree(t->rchild); delete t; t=NULL; } } void converse(Tree* t) { Node temp; Stack* s; Tree* p; Tree* temp_point=NULL; s=create_stack(); p=t; while(p!=NULL || !empty_stack(s)) { if(p) { temp.p=p; temp.count=0; push_stack(s,temp); p=p->lchild; } else { pop_stack(s,&temp); p=temp.p; if(temp.count==0) { temp.count=1; temp.p=p; push_stack(s,temp); p=p->rchild; } else { //此时该访问p节点，它的左右孩子都调整完毕了 temp_point=p->lchild; p->lchild=p->rchild; p->rchild=temp_point; p=NULL; } } } delete s; } void inorder(Tree* t) { if(t) { inorder(t->lchild); cout<<t->value<<" "; inorder(t->rchild); } } int main(void) { Tree* root; root=create_tree(); cout<<"before..."<<endl; inorder(root); cout<<endl; cout<<"after..."<<endl; converse(root); inorder(root); cout<<endl; free_tree(root); return 0; }
先序输入给定的树, 8 6 5 0 0 7 0 0 10 9 0 0 11 0 0