结果要求如下:例如输入:先序ABCDE,中序BADCE
输出:后序BDECA并打印二叉树
A
|_B
|_C
|_D
|_E
代码如下:
#include
#include
using namespace std;
struct MyTreeNode
{
int col;//打印结果中的列
int row;//打印结果中的行
//char val ;
char data;
MyTreeNode rightChild , *leftChild;
} ;
MyTreeNode rebuild(string preorderTraverse,string inorderTraverse)
{
int i , len ;
MyTreeNode *root = new MyTreeNode() ;
root->data = preorderTraverse[0] ;
//cout << pre<< " " << mid << endl ;
len = inorderTraverse.length() ;
for(i=0;i
{
if(preorderTraverse[0]==inorderTraverse[i])
{
if(i!=0)
{
root->leftChild = rebuild(preorderTraverse.substr(1,i),inorderTraverse.substr(0,i)); //左子树
}
else{
root->leftChild = NULL ;
}
if(i!=len-1)
{
root->rightChild = rebuild(preorderTraverse.substr(i+1,len-1-i),inorderTraverse.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<length0;i++)
{//结果数组的行
for(int j=0;j<length1;j++)
{//结果数组的列
unsigned char p=array[i][j];
if(p==0)
{
//若字符值为0则换为空格
p=' ';
}
cout<<(unsigned char)p;
}
cout<<endl;
}
}
//确定每个节点在结果中的行列
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<eCol;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<length0;i++)
{
//结果数组的行
for(int j=0;j<length1;j++)
{
//结果数组的列
unsigned char p=array[i][j];
//若字符值为179竖线
if (p==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<length0;i++)
{// 结果数组的行
for(int j=0;j<length1;j++)
{
//结果数组的列
unsigned char p=array[i][j];
//若字符值为195竖线
if(p==195)
{
//若字符值为195竖横线则查看其下侧字符是否为空白
if(i+1<length0)
{
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 preorderTraverse , inorderTraverse ;
MyTreeNode *root = NULL ;
while(cin>>preorderTraverse>>inorderTraverse)
{
cout<<"后序："<<endl;
MyTreeNode * root ;
root = rebuild(preorderTraverse,inorderTraverse) ;
after(root) ;
}
cout<<"=====preorder traverse print binary tree====="<<endl;
cout<<"================"<<endl;
//先序遍历（计算每个节点打印位置）
preorderTraverse(root,0);
printArray(printResult,9,SPAN*4);
cout<<"================="<<endl;
//先序遍历（填充父子节点到子节点的连线）
preorderForLine(root);
printArray(printResult,9,SPAN*4);
cout<<"===================="<<endl;
//扫描结果数组将其中右侧有横线的竖线替换为竖横线
processAfterOne(printResult,9,SPAN*4);
printArray(printResult,9,SPAN*4);
cout<<"===================="<<endl;
//扫描结果数组将其中的下面没有竖线的竖横线替换为右拐竖线
processAfterTwo(printResult,9,SPAN*4);
printArray(printResult,9,SPAN*4);
cout<<"===================="<<endl;
return 0;
}
