qq_36865094
2016-11-29 08:36
采纳率: 80%
浏览 931

求c++大神帮忙改程序!!!

结果要求如下:例如输入:先序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;

}

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 邀请回答

3条回答 默认 最新

相关推荐 更多相似问题