//bug    last line can not swap with n-1
//http://www.zhihu.com/question/22547591/
 #include
 #include
#include   
#include   
#include   
#include  
#include  
using namespace std;
  int ii=0;
int Find( char x,int size,int zeroIndex)
{
    switch (x)
    {
    case 's': //上移 就是找到零下面的那个数字的位置 也就是序号增加一行 也就是+4
        {
        if ( zeroIndex3)
        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 >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  
struct Binary_node  
{  
    T data;  
    Binary_node* left;  
    Binary_node* right;  
    Binary_node();  
    Binary_node(const T &x);  
};  
    
template  
class Binary_tree  
{  
public:  
    Binary_tree():root(NULL){}; 
    Binary_tree(const Binary_tree&original);  
    Binary_tree & operator=(const Binary_tree&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* get_root() const; 
    void leaf()
   {
    Binary_node *b;
   cout<<"leaf number:"<<_leaf(root)+1<data<<" "<*cur=root;
    Binary_node*p=root;
     queue* > q;  
     Binary_node *b;
    int f=1,r=0;
    T c;
    cin>>c;
    root=new Binary_node; q.push(root);  root->data=c;
   while(c!=-1)
    {
       if(r%2==0)
              {root->left=new Binary_node;  q.push(root->left);}
       else
              {root->right=new Binary_node;  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 p;
int i,j,k=0;
  n=n+1;
 while(n--)
 { m=pow(2,k+1)-1;
   for(i=0;i *b ;
  _fun(root);
  q.push(root);
//while((!p.empty())&&(!q.empty()))
while((q.size()>1))
{  p.pop();
for(i=0;idata<<" "<*b=root;
   _createBiTree(root);
   }  
 
    void lay(int n)                         /*/ 层次打印 /*/
   {  //assert(root)
      int k=1; int m=1;int i=0;
      Binary_node *b=root;
      queue* > 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;idata; 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<data; q.pop();}
else cout<<"#";
       }
      cout<*root) const;  
    int recursive_height(const Binary_node*root) const;  
    void equal(Binary_node*&sub_root,const Binary_node*orig_node);  
    void recursive_reverse(Binary_node * & sub_root);  
    void recursive_clear(Binary_node * & sub_root);  
    void recursive_insert(Binary_node * & sub_root, const T& x);  
    void recursive_inorder(Binary_node * sub_root, void (*visit)(T &));  
    void recursive_preorder(Binary_node * sub_root, void (*visit)(T &));  
    void recursive_postorder(Binary_node * sub_root, void (*visit)(T &)); 
    void _fun(Binary_node * 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 * 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 *&sub_root)
 {
    T c;  
    cin >> c;  
     
/*************/
  if(-1== c)  sub_root = NULL;  
    else  
    {  
        sub_root = new Binary_node; 
        sub_root->data = c;  
        _createBiTree(sub_root->left);  
        _createBiTree(sub_root->right);  
    }  
 
/*************/ 
} 
protected:  
    Binary_node* root;  
    queue* > q;
    
};
////////////////////////////////////////////  

#ifndef BINARY_TREE_CPP_X  
#define BINARY_TREE_CPP_X  
  
template  
Binary_node::Binary_node()  
{  
    left = right = NULL;  
}  
template  
Binary_node::Binary_node(const T &x)  
{  
    left = right = NULL;  
    data = x;  
}  
template  
Binary_tree::Binary_tree(const Binary_tree&original)  
{  
    root = original.get_root();  
}  
template  
void Binary_tree::recursive_preorder(Binary_node*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  
void Binary_tree::preorder(void (*visit)(T&))  
{//先序遍历  
    recursive_preorder(root, visit);  
}
template  
void Binary_tree::recursive_inorder(Binary_node*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  
void Binary_tree::inorder(void (*visit)(T&))  
{//中序遍历  
    recursive_inorder(root, visit);  
}  
 
template  
void Binary_tree::recursive_postorder(Binary_node*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  
void Binary_tree::postorder(void (*visit)(T&))  
{//后序遍历  
    recursive_postorder(root, visit);  
}  
 
  
 
//return tree height, if only one node then return 1  
template  
int Binary_tree::height() const  
{  
    return recursive_height(root);  
}  
#endif
#define max MAX  
template  
Comparable MAX(const Comparable& a, const Comparable& b)  
{  
    return a > b ? a : b;  
}  
template  
int Binary_tree::recursive_height(const Binary_node*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  
int Binary_tree::size() const  
{  
    return recursive_size(root);  
}  
template  
int Binary_tree::recursive_size(const Binary_node*root) const  
{  
    if(root == NULL)  
        return 0;   
    else  
        return 1 + recursive_size(root->left) + recursive_size(root->right) ;  
}  
//the tree is empty ?  
template  
bool Binary_tree::empty() const  
{  
    return root == NULL;  
}  
//insert x to the tree  
template  
void Binary_tree::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  
void Binary_tree::recursive_insert(Binary_node*&sub_root, const T& x)  
{  
    if(sub_root == NULL)  
    {  
        Binary_node* ins_data = new Binary_node(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  
Binary_tree::~Binary_tree()  
{  
    clear();  
}  
template  
void Binary_tree::clear()  
{  
    recursive_clear(root);  
}  
/*/ recursive function for destroy tree /*/ 
template  
void Binary_tree::recursive_clear(Binary_node*&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  
const Binary_node* Binary_tree::get_root() const  
{  
    return root;  
}  
/*/ deep copy /*/ 
template  
Binary_tree& Binary_tree::operator =(const Binary_tree&original)  
{  
    equal(root, original.get_root());  
    return *this;  
}  
template  
void Binary_tree::equal(Binary_node*&sub_root,const Binary_node*orig_node)  
{  
    if(empty())  
        sub_root = new Binary_node(orig_node->data);  
    if(orig_node->left!=NULL)  
    {  
        sub_root->left = new Binary_node(orig_node->left->data);  
        equal(root->left, orig_node->left);  
    }  
    if(orig_node->right!=NULL)  
    {  
        sub_root->right = new Binary_node(orig_node->right->data);  
        equal(root->right, orig_node->right);  
    }  
}  
 
template  
void Binary_tree::reverse()  
{  
    recursive_reverse(root);  
}  
template  
void Binary_tree::recursive_reverse(Binary_node * & sub_root)  
{  
    if(sub_root!=NULL)  
    {  
        Binary_node* 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 dd;  
//dd.createBiTree(); 
dd.createlay();
dd.lay(9); 
}
void print( int& x);  
void test11()  
{  
    Binary_tree dd;  
    dd.insert(1);  
    dd.insert(2);  
    dd.insert(3);  
   
 dd.insert(4);  
    dd.insert(5);  
    dd.insert(6);  
    dd.insert(7);
   /***************  
Binary_tree ww;  
    ww = dd;  
    ww.insert(10);  
     ww.insert(7);  
     cout<<"preorder:";  
    dd.preorder(print);  
     cout<left->data<<"left"<left==NULL&&b->right==NULL){cout<<"#"<data<<" "<left->data!=2&&b->left->data!=3){cout<<"#"<data<<" "<
创新互联公司一直通过网站建设和网站营销帮助企业获得更多客户资源。 以"深度挖掘，量身打造，注重实效"的一站式服务，以网站设计、做网站、移动互联产品、成都营销网站建设服务为核心业务。十载网站制作的经验，使用新网站建设技术，全新开发出的标准网站，不但价格便宜而且实用、灵活，特别适合中小公司网站制作。网站管理系统简单易用，维护方便，您可以完全操作网站资料，是中小公司快速网站建设的选择。
            
            
                                

                    文章标题：小代码二叉树添加树状打印及倒立打印                    

                    URL分享：http://chengdu.cdxwcx.cn/article/pegiee.html