二叉の木が知られています.最初の順序は連続データを巡回し、出力後はシーケンスを巡回します.
#include
#include
const int N=20;
char s1[N], s2[N], ans[N];//s1[N],s2[N]
void build(int n, char* s1, char* s2, char* s)
{
if(n <= 0) return;
int p = strchr(s2, s1[0]) - s2;//
build(p, s1+1, s2, s);//
build(n-p-1, s1+p+1, s2+p+1, s+p);//
s[n-1] = s1[0];//
}
int main()
{
while(scanf("%s%s",s1, s2) == 2)
{
int n= strlen(s1);
build(n, s1,s2, ans);
ans[n] = '\0';
printf("%s
",ans);
return 0;
}
}
上記のコードを変形すると、既知の中の順序と後の順序が連続データを巡回するコードを得ることができます.#include
#include
const int N=20;
char s1[N], s2[N], ans[N];//s1[N],s2[N]
void build(int n, char* s1, char* s2, char* s)
{
if(n <= 0) return;
int p = strchr(s1, s2[n-1]) - s1;// s1
s[0] = s2[n-1];//
build(p, s1, s2, s+1);//
build(n-p-1, s1+p+1, s2+p, s+p+1);//
}
int main()
{
while(scanf("%s%s",s1, s2) == 2)
{
int n= strlen(s1);
build(n, s1,s2, ans);
ans[n] = '\0';
printf("%s
",ans);
return 0;
}
}
違いはbuildの違いだけです.よく比較すれば分かります.次のコードを与えます.
#include
#include
#include
using namespace std;
struct BinaryTreeNode
{
char c;
BinaryTreeNode *lchild, *rchild;
BinaryTreeNode()
{
lchild = NULL, rchild = NULL;
}
};
struct BinaryTreeNode *root1,*root2;
char preorder[100], inorder[100], postorder[100];
void preSearch(BinaryTreeNode *root) //
{
if(root != NULL)
{
printf("%c", root->c);
preSearch(root->lchild);
preSearch(root->rchild);
}
return ;
}
void midSearch(BinaryTreeNode *root) //
{
if(root != NULL)
{
midSearch(root->lchild);
printf("%c", root->c);
midSearch(root->rchild);
}
return ;
}
void postSearch(BinaryTreeNode *root) //
{
if(root != NULL)
{
postSearch(root->lchild);
postSearch(root->rchild);
printf("%c", root->c);
}
return ;
}
void BuildTreeFromPreAndMid(BinaryTreeNode * &root, int ll, int lr, int len, int &now)//
{
root = new BinaryTreeNode();
root->c = *(preorder + now);
int pos = (int)(strchr(inorder, *(preorder + now)) - inorder); //
now++;
if(now >= len)
return ;
if(pos - 1 >= ll)
{
BinaryTreeNode *t = new BinaryTreeNode();
root->lchild = t;
BuildTreeFromPreAndMid(root->lchild, ll, pos - 1, len, now);
}
if(pos + 1 <= lr)
{
BinaryTreeNode *t = new BinaryTreeNode();
root->rchild = t;
BuildTreeFromPreAndMid(root->rchild, pos + 1, lr, len, now);
}
}
void BuildTreeFromPostAndMid(BinaryTreeNode * &root, int ll, int lr, int len, int &now)//
{
root = new BinaryTreeNode();
root->c = *(postorder + now);
int pos = (int)(strchr(inorder, *(postorder + now)) - inorder);
now--;
if(now < 0)
return ;
if(pos + 1 <= lr)
{
BinaryTreeNode *t = new BinaryTreeNode();
root->rchild = t;
BuildTreeFromPostAndMid(root->rchild, pos + 1, lr, len, now);
}
if(pos - 1 >= ll)
{
BinaryTreeNode *t = new BinaryTreeNode();
root->lchild = t;
BuildTreeFromPostAndMid(root->lchild, ll, pos - 1, len, now);
}
}
//
inline void DeleteBinaryTree(BinaryTreeNode * &root)
{
if(root)
{
DeleteBinaryTree(root->lchild); //
DeleteBinaryTree(root->rchild); //
delete root; //
}
}
int main(void)
{
gets(preorder);
gets(inorder);
//gets(postorder);
int now = 0;
BuildTreeFromPreAndMid(root1, 0, strlen(preorder) - 1, strlen(preorder), now);
//int now2 = strlen(postorder)-1;
//BuildTreeFromPostAndMid(root2, 0, strlen(postorder) - 1, strlen(postorder), now2);
postSearch(root1);
puts("");
DeleteBinaryTree(root1);
/*preSearch(root2);
puts("");
DeleteBinaryTree(root2);*/
return 0;
}