对于该问题,写了一串代码,但接近根节点时容易出错(输出时发现sum 和 sum2都有错误)
#include<bits/stdc++.h>
#define N 40
using namespace std;
typedef char ElemType;
struct Node{
Node *right;
Node *left;
ElemType data;
};
typedef Node* BiTree;
void preTraver(BiTree &T)
{
if(T){
cout<<T->data<<" ";
preTraver(T->left);
preTraver(T->right);
}
}
void Match_BiTree(char s1[],char s2[],BiTree &T)
{
int len = strlen(s1),sum1 = 0,sum2,i,j;
//接收到本层的根节点
char root = s2[len - 1];
T = new Node;
T->data = root;
T->left = T->right = NULL;
//叶子节点
if(len == 1){
return;
}
//计算左树的元素数量
for(i=0;i<len;i++){
if(s1[i] != root)
sum1++;
else
break;
}
sum2 = len - sum1 - 1;
//将当前根节点的左树和右树分开
char leftMid[sum1],leftRear[sum1],rightMid[sum2],rightRear[sum2];
for(i=0;i<sum1;i++){
leftMid[i] = s1[i];
}
i++;
for(j=0;j<sum2;i++,j++){
rightMid[j] = s1[i];
}
for(i=0;i<sum1;i++){
leftRear[i] = s2[i];
}
for(j=0;j<sum2;i++,j++){
rightRear[j] = s2[i];
}
if(sum1>0)
Match_BiTree(leftMid,leftRear,T->left);
if(sum2>0)
Match_BiTree(rightMid,rightRear,T->right);
}
int main()
{
BiTree T;
char s1[N],s2[N];
cin>>s1>>s2;
Match_BiTree(s1,s2,T);
preTraver(T);
return 0;
}
1. 在codeblocks运行会进死循环 2. 当越接近根节点,sum1 和 sum2和len的数量都不对 3. 当我只输入 d d(一次到根节点的情况却没有问题)
(自认为逻辑没有大的问题)主要就是利用后序的最后一个肯定为根节点,然后用递归依次建立二叉树的。
可以告诉我当前代码的问题,或者哪里有逻辑上的Bug吧