小代码 二叉树 添加树状打印及倒立打印

  //bug    last line can not swap with n-1
//http://www.zhihu.com/question/22547591/
 #include<iostream>
 #include<queue>
#include <queue>  
#include <vector>  
#include <list>  
#include <math.h> 
#include <cstdio> 
using namespace std;
  int ii=0;
int Find( char x,int size,int zeroIndex)
{
    switch (x)
    {
    case 's': //上移 就是找到零下面的那个数字的位置 也就是序号增加一行 也就是+4
        {
        if ( zeroIndex<size - 4)
        {
            return zeroIndex + 4;
        }
        }
        break;
    case 'x': //下移
        {
//        if (zeroIndex<size-4 && zeroIndex>3)
        if (  zeroIndex>3)
        {
            return zeroIndex - 4;
        }
        }
        break;
    case 'c': 
        {
        if ( zeroIndex%4!=0 )
        {
            return zeroIndex - 1;
        }
        }
        break;
    case 'z':  //左移 主要是判断空白是否在右边缘
        {
        if (zeroIndex%4!=3)
        {
            return zeroIndex + 1;
        }
        }
        break;
    default:
        break;
    }   
    return -1;
}
 
 
//交换数组中zero和next的位置
void SwapIndex(int *ary,int zero, int next)
{
    if (-1 == next)
    {
        return ;
    }
    int t = ary[zero];
    ary[zero] = ary[next];
    ary[next] = t; 
}//DLR
 
void Update(int *ary, int size,char com)
{
    int zeroIndex = 0; //零的序号
    for (int i = 0.; i< size ; i++)
    {
        if (ary[i] == 0)
        {
            zeroIndex = i;
            break;
        }
    }
     
    int nextIndex = Find(com,size,zeroIndex); //获取跟零相邻(根据com不同 取上下左右)的那个数字的序号
    SwapIndex(ary,zeroIndex,nextIndex);
 
}
 
void Show(int *ary, int size)
{  ii++;
    for (int i  = 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):";
}
 
bool ProcessCommand(int *ary, int size,  char com)
{
   //    system("cls");
    Update(ary,size,com); //更新地图
    Show(ary,size); //显示新的地图
    return true;
}
 
 
char GetCommand() //假设只返回4个值 代表四个方向
{
//int test = 1;
char  test='s';
cin>>test;//先测试一下
return test;
}
 
 
void Process(int *ary, int size)
{
   /// int com = 0;
   char  com='s';
    while(ProcessCommand(ary,size,com))
    {
         com = GetCommand();    
    }
 
}
 
 
int pintu()
{
    int ary[16]; //数字0 代表空白
    for (int i=0;i<16; i++)
    {
        ary[i] = i;
    }
    Process(ary,16);
    return 0;
}


















/////////////////////////////////////////////////////////////////////////


















template<class T>  
struct Binary_node  
{  
    T data;  
    Binary_node<T>* left;  
    Binary_node<T>* right;  
    Binary_node();  
    Binary_node(const T &x);  
};  
    
template<class T>  
class Binary_tree  
{  
public:  
    Binary_tree():root(NULL){}; 
    Binary_tree(const Binary_tree<T>&original);  
    Binary_tree & operator=(const Binary_tree<T>&original); 
    ~Binary_tree();   
    bool empty() const;  
    void preorder(void (*visit)(T &));  /*/ DLR   /*/ 
    void inorder(void  (*visit)(T &));  /*/ LDR  /*/
    void postorder(void (*visit)(T &)); /*/ LRD  /*/ 
    int size() const;                       /*/ Binary_tree大小/*/      
    int height() const;  
    void clear();  
    void insert(const T& x);  
    void reverse();                         /*/ 镜像翻转 /*/
    const Binary_node<T>* get_root() const; 
    void leaf()
   {
    Binary_node<T> *b;
   cout<<"leaf number:"<<_leaf(root)+1<<endl;
   cout<<"and the leaf element :"<<endl;
while(!q.empty())
{
    b=q.front(); cout<<b->data<<" "<<endl;q.pop();
 }  
   }
 void createlay()
   {
    Binary_node<T>*cur=root;
    Binary_node<T>*p=root;
     queue<Binary_node<T>* > q;  
     Binary_node<T> *b;
    int f=1,r=0;
    T c;
    cin>>c;
    root=new Binary_node<T>; q.push(root);  root->data=c;
   while(c!=-1)
    {
       if(r%2==0)
              {root->left=new Binary_node<T>;  q.push(root->left);}
       else
              {root->right=new Binary_node<T>;  q.push(root->right);}
       if(r%2==1)f++;if(f%2==0)root=q.front(); q.pop();
      r++;
    cin>>c;
    }
   }  
void fun(int n)
{ 
int m=pow(2,n)-1; queue<int> p;
int i,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++;
 }
  //the end only add pow(2,n)-2 number ;
 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();
} 
 
}
   void createBiTree()
   {
    //Binary_node<T>*b=root;
   _createBiTree(root);
   }  
 
    void lay(int n)                         /*/ 层次打印 /*/
   {  //assert(root)
      int k=1; int m=1;int i=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();}
else cout<<"#";
       }
      cout<<endl;
      n=n/2; 
      k++;
   }
 

}

    //一些递归辅助函数  
private:      
    int recursive_size(const Binary_node<T>*root) const;  
    int recursive_height(const Binary_node<T>*root) const;  
    void equal(Binary_node<T>*&sub_root,const Binary_node<T>*orig_node);  
    void recursive_reverse(Binary_node<T> * & sub_root);  
    void recursive_clear(Binary_node<T> * & sub_root);  
    void recursive_insert(Binary_node<T> * & sub_root, const T& x);  
    void recursive_inorder(Binary_node<T> * sub_root, void (*visit)(T &));  
    void recursive_preorder(Binary_node<T> * sub_root, void (*visit)(T &));  
    void recursive_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) return 0;  
    if(NULL == sub_root->left&& NULL == sub_root->right)  
       { return 1;  q.push(sub_root);}
    return _leaf(sub_root->left) + _leaf(sub_root->right); 
}
 void _createBiTree(Binary_node<T> *&sub_root)
 {
    T c;  
    cin >> c;  
     
/*************/
  if(-1== c)  sub_root = NULL;  
    else  
    {  
        sub_root = new Binary_node<T>; 
        sub_root->data = c;  
        _createBiTree(sub_root->left);  
        _createBiTree(sub_root->right);  
    }  
 
/*************/ 
} 
protected:  
    Binary_node<T>* root;  
    queue<Binary_node<T>* > q;
    
};
////////////////////////////////////////////  

#ifndef BINARY_TREE_CPP_X  
#define BINARY_TREE_CPP_X  
  
template<class T>  
Binary_node<T>::Binary_node()  
{  
    left = right = NULL;  
}  
template<class T>  
Binary_node<T>::Binary_node(const T &x)  
{  
    left = right = NULL;  
    data = x;  
}  
template<class T>  
Binary_tree<T>::Binary_tree(const Binary_tree<T>&original)  
{  
    root = original.get_root();  
}  
template<class T>  
void Binary_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<class T>  
void Binary_tree<T>::preorder(void (*visit)(T&))  
{//先序遍历  
    recursive_preorder(root, visit);  
}
template<class T>  
void Binary_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<class T>  
void Binary_tree<T>::inorder(void (*visit)(T&))  
{//中序遍历  
    recursive_inorder(root, visit);  
}  
 
template<class T>  
void Binary_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<class T>  
void Binary_tree<T>::postorder(void (*visit)(T&))  
{//后序遍历  
    recursive_postorder(root, visit);  
}  
 
  
 
//return tree height, if only one node then return 1  
template<class T>  
int Binary_tree<T>::height() const  
{  
    return recursive_height(root);  
}  
#endif
#define max MAX  
template<class Comparable>  
Comparable MAX(const Comparable& a, const Comparable& b)  
{  
    return a > b ? a : b;  
}  
template<class T>  
int Binary_tree<T>::recursive_height(const Binary_node<T>*root) const  
{  
    if(root == NULL)  
        return 0;  
    else  
        return 1 + max(recursive_height(root->left) , recursive_height(root->right)) ;  
}  
#undef max  
 
//return the size of tree  
template<class T>  
int Binary_tree<T>::size() const  
{  
    return recursive_size(root);  
}  
template<class T>  
int Binary_tree<T>::recursive_size(const Binary_node<T>*root) const  
{  
    if(root == NULL)  
        return 0;   
    else  
        return 1 + recursive_size(root->left) + recursive_size(root->right) ;  
}  
//the tree is empty ?  
template<class T>  
bool Binary_tree<T>::empty() const  
{  
    return root == NULL;  
}  
//insert x to the tree  
template<class T>  
void Binary_tree<T>::insert(const T& x)  
{  
    recursive_insert(root, x);  
}  
//the recursive function of insert,  
//insert x in the less height side,  
//if both sides are same height then insert to the left  
//第一个参数必须使用引用否则插入失败,而其他不涉及数据改动的函数则不需要  
//引用传参时不会发生值拷贝,如果不加引用,会先在函数的栈空间拷贝一个root,但当函数  
//结束时这个拷贝就会被销毁,所以会导致插入失败  
template<class T>  
void Binary_tree<T>::recursive_insert(Binary_node<T>*&sub_root, const T& x)  
{  
    if(sub_root == NULL)  
    {  
        Binary_node<T>* ins_data = new Binary_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);  
        else  
            recursive_insert(sub_root->left, x);  
    }  
}  
 


template<class T>  
Binary_tree<T>::~Binary_tree()  
{  
    clear();  
}  
template<class T>  
void Binary_tree<T>::clear()  
{  
    recursive_clear(root);  
}  
/*/ recursive function for destroy tree /*/ 
template<class T>  
void Binary_tree<T>::recursive_clear(Binary_node<T>*&sub_root)  
{/*/两个版本都OK /*/ 
#if 0  
    if(sub_root != NULL)  
    {  
        recursive_clear(sub_root->left);  
        recursive_clear(sub_root->right);  
        delete sub_root;  
        sub_root = NULL;  
    }  
#else  
    if(sub_root->left!=NULL)  
        recursive_clear(sub_root->left);  
    if(sub_root->right!=NULL)  
        recursive_clear(sub_root->right);  
    delete sub_root;  
    sub_root = NULL;  
#endif  
}  
/*/  get the root /*/ 
template<class T>  
const Binary_node<T>* Binary_tree<T>::get_root() const  
{  
    return root;  
}  
/*/ deep copy /*/ 
template<class T>  
Binary_tree<T>& Binary_tree<T>::operator =(const Binary_tree<T>&original)  
{  
    equal(root, original.get_root());  
    return *this;  
}  
template<class T>  
void Binary_tree<T>::equal(Binary_node<T>*&sub_root,const Binary_node<T>*orig_node)  
{  
    if(empty())  
        sub_root = new Binary_node<T>(orig_node->data);  
    if(orig_node->left!=NULL)  
    {  
        sub_root->left = new Binary_node<T>(orig_node->left->data);  
        equal(root->left, orig_node->left);  
    }  
    if(orig_node->right!=NULL)  
    {  
        sub_root->right = new Binary_node<T>(orig_node->right->data);  
        equal(root->right, orig_node->right);  
    }  
}  
 
template<class T>  
void Binary_tree<T>::reverse()  
{  
    recursive_reverse(root);  
}  
template<class T>  
void Binary_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);  
    }  
}  
 
 
  void test10()
{
Binary_tree<int> dd;  
//dd.createBiTree(); 
dd.createlay();
dd.lay(9); 
}
void print( int& x);  
void test11()  
{  
    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;    
}  
void print( int& x)  
{  
    cout<<x<<" ";  
} 
 
 
int main()
{
//pintu();
test11();
    return 0;  
}  

/////////// /****************
   
//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();}