#include
#include
using namespace std;
struct MyTreeNode
{
int col;//打印结果中的列
int row;//打印结果中的行
char data;
MyTreeNode rightChild , *leftChild;
};
MyTreeNode rebuild(string preorder,string inorder)//先序，中序
{
int i , len ;
MyTreeNode *root = new MyTreeNode() ;
root->data = preorder[0] ;
len = inorder.length() ;
for(i=0;i
{
if(preorder[0]==inorder[i])
{
if(i!=0)
{ //左子树
root->leftChild=rebuild(preorder.substr(1,i),inorder.substr(0,i));
}
else
{
root->leftChild = NULL ;
}
if(i!=len-1)
{//右子树
root->rightChild=rebuild(preorder.substr(i+1,len-1-i),inorder.substr(i+1,len-1-i));
}
else
{
root->rightChild = NULL ;
}
}
}
return root ;
};
void after(MyTreeNode *root)
{
if(root==NULL)return ;
{
if(root->leftChild!=NULL)
after(root->leftChild) ;
if(root->rightChild!=NULL)
after(root->rightChild) ;
cout << root->data;
}
};
const int SPAN=4;//每一层的横向缩进值为4
unsigned char printResult[9][SPAN*4];//打印结果数组
int currRow=0;//第一轮行计数器
void printArray(unsigned char array[][SPAN*4],int length0,int length1)
{//打印结果数组
for(int i=0;i
{//结果数组的行
for(int j=0;j
{//结果数组的列
unsigned char p=array[i][j];
if(p==0)
{//若字符值为0则换为空格
p=' ';
}
cout
}
cout
}
}
//确定每个节点在结果中的行列
void preorderTraverse(MyTreeNode*root,int level)
{
if(root==NULL)return;
root->row=currRow;
currRow++;
root->col=level*SPAN;
printResult[root->row][root->col]=root->data;
preorderTraverse(root->leftChild,level+1);
preorderTraverse(root->rightChild,level+1);
}
//填充父节点与子节点的连线
void preorderForLine(MyTreeNode*root)
{
if(root==NULL)return;
int sCol=root->col;
int sRow=root->row;
if(root->leftChild!=NULL)
{//当前子树根节点到左子节点的连线
int eCol=root->leftChild->col;
int eRow=root->leftChild->row;
for(int i=sRow+1;i<=eRow;i++)
{//竖线
printResult[i][sCol]=179;
}
for(int i=sCol+1;i
{ //横线
printResult[eRow][i]=196;
}
}
if(root->rightChild!=NULL)
{//当前子树根节点到右子节点的连线
int eCol=root->rightChild->col;
int eRow=root->rightChild->row;
for(int i=sRow+1;i<eRow;i++)
{//竖线
printResult[i][sCol]=179;
}
for(int i=sCol+1;i<eCol;i++)
{//横线
printResult[eRow][i]=196;
}
}
preorderForLine(root->leftChild);
preorderForLine(root->rightChild);
}
//扫描结果数组将其右侧有横线的竖线替换为竖横线
void processAfterOne(unsigned char array[][SPAN*4],int length0,int length1)
{
for(int i=0;i
{//结果数组的行
for(int j=0;j
{//结果数组的列
unsigned char p=array[i][j];
if (p==179)//若字符值为179竖线
{//若字符值为179竖线则查看其右侧字符是否为横线
unsigned char pr=array[i][j+1];
if(pr==196)
{//若其右侧为横线则将其替换为竖横线
array[i][j]=195;
}
}
}
}
}
//扫描结果数组将其中下面没有竖横线替换为右拐竖线
void processAfterTwo(unsigned char array[][SPAN*4],int length0,int length1)
{
for(int i=0;i
{// 结果数组的行
for(int j=0;j
{//结果数组的列
unsigned char p=array[i][j];
if(p==195) //若字符值为195竖线
{//若字符值为195竖横线则查看其下侧字符是否为空白
if(i+1
{
unsigned char pr=array[i+1][j];
if(pr=0)
{//若其右侧为横线则将其替换为竖横线
array[i][j]=192;
}
}
else
{//若其位于最后一行则将其替代为右拐竖线
array[i][j]=192;
}
}
}
}
}
int main(int argc, char *argv[])
{
system("chcp 437>nul.");
string preorder , inorder ;
MyTreeNode *root = NULL ;
cout<<"please input preorder:"<
cin>>preorder;
cout<<"please input inorder:"<
cin>>inorder;
cout<<"post:"<<endl;
root = rebuild(preorder,inorder) ;
after(root) ;
cout<<endl;
cout<<"=====preorder traverse print binary tree====="<<endl;
cout<<"================"<<endl;
//先序遍历（计算每个节点打印位置）
preorderTraverse(root,0);
printArray(printResult,preorder.length(),SPAN*4);
cout<<"================="<<endl;
//先序遍历（填充父子节点到子节点的连线）
preorderForLine(root);
printArray(printResult,preorder.length(),SPAN*4);
cout<<"===================="<<endl;
//扫描结果数组将其中右侧有横线的竖线替换为竖横线
processAfterOne(printResult,preorder.length(),SPAN*4);
printArray(printResult,preorder.length(),SPAN*4);
cout<<"===================="<<endl;
//扫描结果数组将其中的下面没有竖线的竖横线替换为右拐竖线
processAfterTwo(printResult,preorder.length(),SPAN*4);
printArray(printResult,preorder.length(),SPAN*4);
cout<<"===================="<<endl;
return 0;
}
