二叉木再帰遍歴既知先序、中序求後序シーケンス、既知中序、後序求先序シーケンス例
30001 ワード
ツリーデータ構造の定義
ツリー再帰遍歴
既知のシーケンス、中シーケンス後シーケンスを求める
既知の中序、後序は先序のシーケンスを求めます
typedef char TElemType;
typedef struct TreeNode
{
struct TreeNode *lchild;
struct TreeNode *rchild;
TElemType data;
}TreeNode,*Tree;
ツリー再帰遍歴
void PreOrderTraverse(Tree &T)
{
if (T) {
printf("%c",T->data);
}
if (T->lchild) {
PreOrderTraverse(T->lchild);
}
if (T->rchild) {
PreOrderTraverse(T->rchild);
}
}
void InOrderTraverse(Tree &T)
{
if (T->lchild) {
InOrderTraverse(T->lchild);
}
printf("%c",T->data);
if (T->rchild) {
InOrderTraverse(T->rchild);
}
}
void PostOrderTraverse(Tree &T)
{
if (T->lchild) {
PostOrderTraverse(T->lchild);
}
if (T->rchild) {
PostOrderTraverse(T->rchild);
}
printf("%c",T->data);
}
既知のシーケンス、中シーケンス後シーケンスを求める
#include
typedef char TElemType;
typedef struct TreeNode
{
struct TreeNode *lchild;
struct TreeNode *rchild;
TElemType data;
}TreeNode,*Tree;
Tree create(TElemType data);
Tree BuildBiTree(int s1,int e1,int s2,int e2);
void PostTraverse(Tree &T);
char pre[30],in[30];
int main()
{
while (scanf("%s",pre)!=EOF) {
scanf("%s",in);
int l1=(int)strlen(pre);
int l2=(int)strlen(in);
Tree T=BuildBiTree(0, l1-1, 0, l2-1);
PostTraverse(T);
printf("
");
}
return 0;
}
Tree create(TElemType data)
{
Tree T=new TreeNode;
T->lchild=T->rchild=NULL;
T->data=data;
return T;
}
Tree BuildBiTree(int s1,int e1,int s2,int e2)
{
Tree T=create(pre[s1]);
int rootposition=0;
for (int i=s2; i<=e2; i++) {
if (pre[s1]==in[i]) {
rootposition=i;
break;
}
}
if (rootposition!=s2) {
T->lchild=BuildBiTree(s1+1, s1+rootposition-s2, s2, rootposition-1);
}
if (rootposition!=e2) {
T->rchild=BuildBiTree(s1+rootposition-s2+1, e1, rootposition+1, e2);
}
return T;
}
void PostTraverse(Tree &T)
{
if (T->lchild) {
PostTraverse(T->lchild);
}
if (T->rchild) {
PostTraverse(T->rchild);
}
printf("%c",T->data);
}
既知の中序、後序は先序のシーケンスを求めます
#include
typedef char TElemType;
typedef struct TreeNode
{
struct TreeNode *lchild;
struct TreeNode *rchild;
TElemType data;
}TreeNode,*Tree;
Tree create(TElemType data);
Tree BuildBiTree(int s1,int e1,int s2,int e2);
void PreOrderTraverse(Tree &T);
char in[30],post[30];
int main()
{
while (scanf("%s",in)!=EOF) {
scanf("%s",post);
int l1=(int)strlen(in);
int l2=(int)strlen(post);
Tree T=BuildBiTree(0, l1-1, 0, l2-1);
PreOrderTraverse(T);
printf("
");
}
return 0;
}
Tree create(TElemType data)
{
Tree T=new TreeNode;
T->lchild=T->rchild=NULL;
T->data=data;
return T;
}
Tree BuildBiTree(int s1,int e1,int s2,int e2)
{
Tree T=create(post[e2]);
int rootposition=0;
for (int i=s1; i<=e1; i++) {
if (post[e2]==in[i]) {
rootposition=i;
break;
}
}
if (rootposition!=s1) {
T->lchild=BuildBiTree(s1, rootposition-1, s2, s2+rootposition-s1-1);
}
if (rootposition!=e1) {
T->rchild=BuildBiTree(rootposition+1, e1, s2+rootposition-s1, e2-1);
}
return T;
}
void PreOrderTraverse(Tree &T)
{
if (T) {
printf("%c",T->data);
}
if (T->lchild) {
PreOrderTraverse(T->lchild);
}
if (T->rchild) {
PreOrderTraverse(T->rchild);
}
}