二叉木再帰遍歴既知先序、中序求後序シーケンス、既知中序、後序求先序シーケンス例

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); } }