データ構造(陳越、何欽銘)--第四周のプログラミング作業

04-木4は同一の二叉検索ツリーかどうか(25分)
挿入されたシーケンスを指定すると、一本の二叉検索ツリーを一意に決定することができます.しかし、与えられた一本の二叉検索ツリーは、複数の異なる挿入シーケンスから得ることができる.例えば、最初に空だった二叉探索ツリーをシーケンス｛2,1,3｝と｛2,3,1｝で挿入すると、同じ結果が得られる.入力された各種の挿入シーケンスについては、同じツリーを生成できるかどうかを判断する必要があります.
入力形式:いくつかのグループのテストデータを入力します.各データの1行目は、2つの正の整数N(≦10)とLを与え、それぞれのシーケンス挿入要素の個数と検査が必要なシーケンス個数である.2行目は、最初の挿入シーケンスとして、N個のスペースで区切られた正の整数を与えます.最後のL行は、行ごとにN個の挿入要素を与え、L個の検査が必要なシーケンスに属する.
簡単のために、各挿入シーケンスは1からNまでの配列であることを保証します.Nが0であるとフラグ入力が終了します.このデータは処理しません.
出力フォーマット:各グループのチェックが必要なシーケンスに対して、生成された二叉検索ツリーが対応する初期シーケンスと同じ場合、「Yes」を出力します.そうでなければ、「No」を出力します.
入力例:4 2 3 1 4 4 4 4 1 2 2 4 1 2 1 2 1 2 1 2 2 2 2 0出力例:Yes No.

#include 
#include 

typedef struct TreeNode *Tree;
struct TreeNode
{
    int Data;
    Tree Left;
    Tree Right;
    int flag;
};

Tree BuildTree(int N);
int Judge(Tree T, int N);
void ResetFlag(Tree T);
void FreeTree(Tree T);
Tree NewNode(int node);
Tree Insert(Tree T, int node);
int Check(Tree T, int node);

int main()
{
    int N, L, i;
    Tree T;

    scanf("%d", &N);
    while(N)
    {
        scanf("%d", &L);

        T = BuildTree(N);
        for(i = 0; i < L; i++)
        {
            if(Judge(T, N))
                printf("Yes
");
            else
                printf("No
");
            ResetFlag(T);
        }
        FreeTree(T);
        scanf("%d", &N);
    }

    return 0;
}

Tree BuildTree(int N)
{
    Tree T;
    int i, node;

    scanf("%d", &node);
    T = NewNode(node);
    for(i = 1; i < N; i++)
    {
        scanf("%d", &node);
        T = Insert(T, node);
    }
    return T;
}

Tree NewNode(int node)
{
    Tree T;
    T = (Tree)malloc(sizeof(struct TreeNode));
    T->Data = node; T->flag = 0; T->Left = T->Right = NULL;
    return T;
}

Tree Insert(Tree T, int node)
{
    if(!T) T = NewNode(node);
    else{
        if(node > T->Data)
            T->Right = Insert(T->Right, node);
        else
            T->Left = Insert(T->Left, node);
    }
    return T;
}

int Judge(Tree T, int N)
{
    int i, node;
    int flag = 0;

    scanf("%d", &node);
    if(node != T->Data)    flag = 1;
    else                   T->flag = 1;

    for(i = 1; i < N; i++){
        scanf("%d", &node);
        if((!flag) && (!Check(T, node)))  flag = 1;
    }
    if(flag)  return 0;
    else return 1;
}

int Check(Tree T, int node)
{
    if(T->flag){
        if(node < T->Data)  return Check(T->Left, node);
        else if(node > T->Data)  return Check(T->Right, node);
        else return 0;
    }
    else{
        if(node == T->Data){
            T->flag = 1;
            return 1;
        }
        else  return 0;
    }
}

void ResetFlag(Tree T)
{
    if(T->Left) ResetFlag(T->Left);
    if(T->Right) ResetFlag(T->Right);
    T->flag = 0;
}

void FreeTree(Tree T)
{
    if(T->Left) FreeTree(T->Left);
    if(T->Right) FreeTree(T->Right);
    free(T);
}

04-ツリー7二叉検索ツリーの操作セット(30分)
本題は与えられた二叉検索ツリーの5種類の常用操作を実現することを要求します.
関数インターフェースの定義:

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

BinTree構造の定義は以下の通りである.

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

関数Insertは、Xを二叉検索ツリーBSTに挿入し、結果ツリーのルートノードポインタを返します.関数Deleteは、Xを二叉検索ツリーBSTから削除し、結果ツリーのルートノードポインタを返します.Xがツリー内にない場合、Not Found行を印刷して元のツリーのルートノードポインタに戻ります.関数Findは、二叉検索ツリーBSTにXを見つけ、そのノードのポインタを返します.見つけられない場合は空のポインタを返します.関数FindMinは、二叉検索ツリーBSTの最小要素ノードのポインタを返します.関数FindMaxは、二叉検索ツリーBSTの中の最大の要素ノードのポインタを返します.
審判試験手順の例:

#include 
#include 

typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

void PreorderTraversal( BinTree BT ); /*     ，     ，     */
void InorderTraversal( BinTree BT );  /*     ，     ，     */

BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );

int main()
{
    BinTree BST, MinP, MaxP, Tmp;
    ElementType X;
    int N, i;

    BST = NULL;
    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    printf("Preorder:"); PreorderTraversal(BST); printf("
");
    MinP = FindMin(BST);
    MaxP = FindMax(BST);
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        Tmp = Find(BST, X);
        if (Tmp == NULL) printf("%d is not found
", X);
        else {
            printf("%d is found
", Tmp->Data);
            if (Tmp==MinP) printf("%d is the smallest key
", Tmp->Data);
            if (Tmp==MaxP) printf("%d is the largest key
", Tmp->Data);
        }
    }
    scanf("%d", &N);
    for( i=0; i<N; i++ ) {
        scanf("%d", &X);
        BST = Delete(BST, X);
    }
    printf("Inorder:"); InorderTraversal(BST); printf("
");

    return 0;
}
/*            */

入力サンプル:
10 5 8 6 2 4 1 0 10 7 5 3 10 5 5 5 5 5 7 0 10 3
出力例:
Prorder:5 2 1 0 4 7 7 10 6 is found 3 is not found 10 is found 10 is the larget key 0 is found 0 is the smalest key 5 is found Not Found Inorder:1 2 4 6 8 9

BinTree Insert( BinTree BST, ElementType X )
{
    if(!BST){
        BST = (BinTree)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }else{
        if(X >= BST->Data){
            BST->Right = Insert(BST->Right, X);
        }else
            BST->Left = Insert(BST->Left, X);
    }
    return BST;
}

BinTree Delete( BinTree BST, ElementType X )
{
    Position item;
    if(!BST){
        printf("Not Found
");
    }else{
        if(X > BST->Data)    BST->Right = Delete(BST->Right, X);
        else if(X < BST->Data)    BST->Left = Delete(BST->Left, X);
        else{
            if((BST->Left)&&(BST->Right)){
                item = FindMin(BST->Right);
                BST->Data = item->Data;
                BST->Right = Delete(BST->Right, BST->Data);
            }
            else{
                item = BST;
                if(!BST->Left)    BST = BST->Right;
                else if(!BST->Right)    BST = BST->Left;
                free(item);
            }
        }
    }
    return BST;
}

Position Find( BinTree BST, ElementType X )
{
    if(!BST)    return NULL;
    else{
        if(X == BST->Data)    return BST;
        else if(X > BST->Data)    return Find(BST->Right, X);
        else    return Find(BST->Left, X);
    }
}

Position FindMin( BinTree BST )
{
    if(BST){
        while(BST->Left)    BST = BST->Left;
    }
    return BST;
}
Position FindMax( BinTree BST )
{
    if(BST){
        while(BST->Right)    BST = BST->Right;
    }
    return BST;
}