//buglastlinecannotswapwithn-1//http://www.zhihu.com/question/22547591/#include<iostream>#include<queue>#include<queue>#include<vector>#include<list>#include<math.h>#include<cstdio>usingnamespacestd;intii=0;intFind(charx,intsize,intzeroIndex){switch(x){case's'://上移就是找到零下面的那个数字的位置也就是序号增加一行也就是+4{if(zeroIndex<size-4){returnzeroIndex+4;}}break;case'x'://下移{//if(zeroIndex<size-4&&zeroIndex>3)if(zeroIndex>3){returnzeroIndex-4;}}break;case'c':{if(zeroIndex%4!=0){returnzeroIndex-1;}}break;case'z'://左移主要是判断空白是否在右边缘{if(zeroIndex%4!=3){returnzeroIndex+1;}}break;default:break;}return-1;}//交换数组中zero和next的位置voidSwapIndex(int*ary,intzero,intnext){if(-1==next){return;}intt=ary[zero];ary[zero]=ary[next];ary[next]=t;}//DLRvoidUpdate(int*ary,intsize,charcom){intzeroIndex=0;//零的序号for(inti=0.;i<size;i++){if(ary[i]==0){zeroIndex=i;break;}}intnextIndex=Find(com,size,zeroIndex);//获取跟零相邻(根据com不同取上下左右)的那个数字的序号SwapIndex(ary,zeroIndex,nextIndex);}voidShow(int*ary,intsize){ii++;for(inti=0;i<size;i++){if(i%4==0)//假设每行4个数字{cout<<endl<<endl;}if(ary[i]!=0){cout<<"\t"<<ary[i];}else{cout<<"\t";}}//cout<<endl<<"请输入方向(1234):";cout<<endl<<""<<ii<<endl<<"请输入方向(sxzc):";}boolProcessCommand(int*ary,intsize,charcom){//system("cls");Update(ary,size,com);//更新地图Show(ary,size);//显示新的地图returntrue;}charGetCommand()//假设只返回4个值代表四个方向{//inttest=1;chartest='s';cin>>test;//先测试一下returntest;}voidProcess(int*ary,intsize){///intcom=0;charcom='s';while(ProcessCommand(ary,size,com)){com=GetCommand();}}intpintu(){intary[16];//数字0代表空白for(inti=0;i<16;i++){ary[i]=i;}Process(ary,16);return0;}/////////////////////////////////////////////////////////////////////////template<classT>structBinary_node{Tdata;Binary_node<T>*left;Binary_node<T>*right;Binary_node();Binary_node(constT&x);};template<classT>classBinary_tree{public:Binary_tree():root(NULL){};Binary_tree(constBinary_tree<T>&original);Binary_tree&operator=(constBinary_tree<T>&original);~Binary_tree();boolempty()const;voidpreorder(void(*visit)(T&));/*/DLR/*/voidinorder(void(*visit)(T&));/*/LDR/*/voidpostorder(void(*visit)(T&));/*/LRD/*/intsize()const;/*/Binary_tree大小/*/intheight()const;voidclear();voidinsert(constT&x);voidreverse();/*/镜像翻转/*/constBinary_node<T>*get_root()const;voidleaf(){Binary_node<T>*b;cout<<"leafnumber:"<<_leaf(root)+1<<endl;cout<<"andtheleafelement:"<<endl;while(!q.empty()){b=q.front();cout<<b->data<<""<<endl;q.pop();}}voidcreatelay(){Binary_node<T>*cur=root;Binary_node<T>*p=root;queue<Binary_node<T>*>q;Binary_node<T>*b;intf=1,r=0;Tc;cin>>c;root=newBinary_node<T>;q.push(root);root->data=c;while(c!=-1){if(r%2==0){root->left=newBinary_node<T>;q.push(root->left);}else{root->right=newBinary_node<T>;q.push(root->right);}if(r%2==1)f++;if(f%2==0)root=q.front();q.pop();r++;cin>>c;}}voidfun(intn){intm=pow(2,n)-1;queue<int>p;inti,j,k=0;n=n+1;while(n--){m=pow(2,k+1)-1;for(i=0;i<m;i++){if(i%2==0)p.push(k);else{p.push(p.front());p.pop();}}k++;}//theendonlyaddpow(2,n)-2number;Binary_node<T>*b;_fun(root);q.push(root);//while((!p.empty())&&(!q.empty()))while((q.size()>1)){p.pop();for(i=0;i<p.front();i++)cout<<"*";p.pop();q.pop();b=q.front();cout<<b->data<<""<<endl;q.pop();}}voidcreateBiTree(){//Binary_node<T>*b=root;_createBiTree(root);}voidlay(intn)/*/层次打印/*/{//assert(root)intk=1;intm=1;inti=0;Binary_node<T>*b=root;queue<Binary_node<T>*>q;q.push(b);while(!q.empty()){b=q.front();if(b->left)q.push(b->left);if(b->right)q.push(b->right);m=pow(2,k-1);for(i=0;i<n/2;i++)cout<<"";cout<<b->data;q.pop();while(--m){for(i=0;i<2*(n/2)+1;i++)cout<<"";if(!q.empty()){b=q.front();if(b->left)q.push(b->left);if(b->right)q.push(b->right);cout<<b->data;q.pop();}elsecout<<"#";}cout<<endl;n=n/2;k++;}}//一些递归辅助函数private:intrecursive_size(constBinary_node<T>*root)const;intrecursive_height(constBinary_node<T>*root)const;voidequal(Binary_node<T>*&sub_root,constBinary_node<T>*orig_node);voidrecursive_reverse(Binary_node<T>*&sub_root);voidrecursive_clear(Binary_node<T>*&sub_root);voidrecursive_insert(Binary_node<T>*&sub_root,constT&x);voidrecursive_inorder(Binary_node<T>*sub_root,void(*visit)(T&));voidrecursive_preorder(Binary_node<T>*sub_root,void(*visit)(T&));voidrecursive_postorder(Binary_node<T>*sub_root,void(*visit)(T&));void_fun(Binary_node<T>*sub_root){if(sub_root==NULL){q.push(root);return;}_fun(sub_root->right);if(sub_root!=NULL){q.push(sub_root);}_fun(sub_root->left);}int_leaf(Binary_node<T>*sub_root){if(NULL==sub_root)return0;if(NULL==sub_root->left&&NULL==sub_root->right){return1;q.push(sub_root);}return_leaf(sub_root->left)+_leaf(sub_root->right);}void_createBiTree(Binary_node<T>*&sub_root){Tc;cin>>c;/*************/if(-1==c)sub_root=NULL;else{sub_root=newBinary_node<T>;sub_root->data=c;_createBiTree(sub_root->left);_createBiTree(sub_root->right);}/*************/}protected:Binary_node<T>*root;queue<Binary_node<T>*>q;};////////////////////////////////////////////#ifndefBINARY_TREE_CPP_X#defineBINARY_TREE_CPP_Xtemplate<classT>Binary_node<T>::Binary_node(){left=right=NULL;}template<classT>Binary_node<T>::Binary_node(constT&x){left=right=NULL;data=x;}template<classT>Binary_tree<T>::Binary_tree(constBinary_tree<T>&original){root=original.get_root();}template<classT>voidBinary_tree<T>::recursive_preorder(Binary_node<T>*sub_root,void(*visit)(T&)){//先序遍历的递归函数if(sub_root!=NULL){(*visit)(sub_root->data);recursive_preorder(sub_root->left,visit);recursive_preorder(sub_root->right,visit);}}template<classT>voidBinary_tree<T>::preorder(void(*visit)(T&)){//先序遍历recursive_preorder(root,visit);}template<classT>voidBinary_tree<T>::recursive_inorder(Binary_node<T>*sub_root,void(*visit)(T&)){//中序遍历的递归函数if(sub_root!=NULL){recursive_inorder(sub_root->left,visit);(*visit)(sub_root->data);recursive_inorder(sub_root->right,visit);}}template<classT>voidBinary_tree<T>::inorder(void(*visit)(T&)){//中序遍历recursive_inorder(root,visit);}template<classT>voidBinary_tree<T>::recursive_postorder(Binary_node<T>*sub_root,void(*visit)(T&)){//后序遍历的递归函数if(sub_root!=NULL){recursive_postorder(sub_root->left,visit);recursive_postorder(sub_root->right,visit);(*visit)(sub_root->data);}}template<classT>voidBinary_tree<T>::postorder(void(*visit)(T&)){//后序遍历recursive_postorder(root,visit);}//returntreeheight,ifonlyonenodethenreturn1template<classT>intBinary_tree<T>::height()const{returnrecursive_height(root);}#endif#definemaxMAXtemplate<classComparable>ComparableMAX(constComparable&a,constComparable&b){returna>b?a:b;}template<classT>intBinary_tree<T>::recursive_height(constBinary_node<T>*root)const{if(root==NULL)return0;elsereturn1+max(recursive_height(root->left),recursive_height(root->right));}#undefmax//returnthesizeoftreetemplate<classT>intBinary_tree<T>::size()const{returnrecursive_size(root);}template<classT>intBinary_tree<T>::recursive_size(constBinary_node<T>*root)const{if(root==NULL)return0;elsereturn1+recursive_size(root->left)+recursive_size(root->right);}//thetreeisempty?template<classT>boolBinary_tree<T>::empty()const{returnroot==NULL;}//insertxtothetreetemplate<classT>voidBinary_tree<T>::insert(constT&x){recursive_insert(root,x);}//therecursivefunctionofinsert,//insertxinthelessheightside,//ifbothsidesaresameheighttheninserttotheleft//第一个参数必须使用引用否则插入失败,而其他不涉及数据改动的函数则不需要//引用传参时不会发生值拷贝,如果不加引用,会先在函数的栈空间拷贝一个root,但当函数//结束时这个拷贝就会被销毁,所以会导致插入失败template<classT>voidBinary_tree<T>::recursive_insert(Binary_node<T>*&sub_root,constT&x){if(sub_root==NULL){Binary_node<T>*ins_data=newBinary_node<T>(x);sub_root=ins_data;return;}else{if(recursive_height(sub_root->left)>recursive_height(sub_root->right))recursive_insert(sub_root->right,x);elserecursive_insert(sub_root->left,x);}}template<classT>Binary_tree<T>::~Binary_tree(){clear();}template<classT>voidBinary_tree<T>::clear(){recursive_clear(root);}/*/recursivefunctionfordestroytree/*/template<classT>voidBinary_tree<T>::recursive_clear(Binary_node<T>*&sub_root){/*/两个版本都OK/*/#if0if(sub_root!=NULL){recursive_clear(sub_root->left);recursive_clear(sub_root->right);deletesub_root;sub_root=NULL;}#elseif(sub_root->left!=NULL)recursive_clear(sub_root->left);if(sub_root->right!=NULL)recursive_clear(sub_root->right);deletesub_root;sub_root=NULL;#endif}/*/gettheroot/*/template<classT>constBinary_node<T>*Binary_tree<T>::get_root()const{returnroot;}/*/deepcopy/*/template<classT>Binary_tree<T>&Binary_tree<T>::operator=(constBinary_tree<T>&original){equal(root,original.get_root());return*this;}template<classT>voidBinary_tree<T>::equal(Binary_node<T>*&sub_root,constBinary_node<T>*orig_node){if(empty())sub_root=newBinary_node<T>(orig_node->data);if(orig_node->left!=NULL){sub_root->left=newBinary_node<T>(orig_node->left->data);equal(root->left,orig_node->left);}if(orig_node->right!=NULL){sub_root->right=newBinary_node<T>(orig_node->right->data);equal(root->right,orig_node->right);}}template<classT>voidBinary_tree<T>::reverse(){recursive_reverse(root);}template<classT>voidBinary_tree<T>::recursive_reverse(Binary_node<T>*&sub_root){if(sub_root!=NULL){Binary_node<T>*temp=NULL;temp=sub_root->left;sub_root->left=sub_root->right;sub_root->right=temp;recursive_reverse(sub_root->left);recursive_reverse(sub_root->right);}}voidtest10(){Binary_tree<int>dd;//dd.createBiTree();dd.createlay();dd.lay(9);}voidprint(int&x);voidtest11(){Binary_tree<int>dd;dd.insert(1);dd.insert(2);dd.insert(3);dd.insert(4);dd.insert(5);dd.insert(6);dd.insert(7);/***************Binary_tree<int>ww;ww=dd;ww.insert(10);ww.insert(7);cout<<"preorder:";dd.preorder(print);cout<<endl;cout<<"preorder:";ww.preorder(print);cout<<endl;dd.lay(9);cout<<endl;dd.reverse();cout<<"preorder:";***************/dd.preorder(print);cout<<endl;dd.lay(9);//dd.leaf();dd.fun(4);cout<<endl;}voidprint(int&x){cout<<x<<"";}intmain(){//pintu();test11();return0;}////////////****************//cout<<b->left->data<<"left"<<endl;//if(b->left==NULL&&b->right==NULL){cout<<"#"<<endl;q.pop();}//else{cout<<b->data<<""<<endl;q.pop();}//if(b->left->data!=2&&b->left->data!=3){cout<<"#"<<endl;q.pop();}//else{cout<<b->data<<""<<endl;q.pop();}