あるノードをルートとするツリーを削除します.

2533 ワード

データ構造二叉の木

プログラムを作成して、二叉ツリーのノード値が単一文字であると仮定して、二叉チェーンストアを採用して、再帰的アルゴリズム求値xのサブツリーを設計し、このサブツリーを削除して、ノードDをサブツリーとして削除した結果を与える.
コード:

#include 
#include 

typedef char ElemType;

typedef struct Node
{
    ElemType data;
    Node *Lchild,*Rchild;
} BiTNode,*BiTree;

BiTree CreateBiTree();//     
BiTNode *Find(BiTree T,char x);
int PostTreeDepth(BiTree T);//         
void PreOrder(BiTree T);//  
void Destory(BiTree T);
void Delete(BiTree T,char x);

int main(void)
{
    char x;
    BiTree root=CreateBiTree();
    getchar();
    printf("        :
");
    PreOrder(root);//  
    printf("
");
    printf("      :%d
",PostTreeDepth(root));
    printf("         
");
    scanf("%c",&x);
    Delete(root,x);
    printf("     %c           :
",x);
    PreOrder(root);
    printf("
");
    printf("     %c         :%d
",x,PostTreeDepth(root));
    return 0;
}

BiTree CreateBiTree()//     
{
    ElemType x;
    BiTree T;
    scanf("%c",&x);
    if(x=='#')
        T=NULL;
    else
    {
        T=(BiTree)malloc(sizeof(BiTNode));
        T->data=x;
        T->Lchild=CreateBiTree();
        T->Rchild=CreateBiTree();
    }
    return T;
}

BiTNode *Find(BiTree T,char x)
{
    BiTNode *p;
    if(T==NULL)
        return NULL;
    else if(T->data==x)
        return T;
    else if(T->Lchild!=NULL&&T->Lchild->data==x)
    {
        p=T->Lchild;
        T->Lchild=NULL;
        return p;
    }
    else if(T->Rchild!=NULL&&T->Rchild->data==x)
    {
        p=T->Rchild;
        T->Rchild=NULL;
        return p;
    }
    else
    {
        p=Find(T->Lchild,x);
        if(p!=NULL)
            return p;
        else
            return Find(T->Rchild,x);
    }
}

int PostTreeDepth(BiTree T)//         
{
    int hl,hr,max;
    if(T!=NULL)
    {
        hl=PostTreeDepth(T->Lchild);
        hr=PostTreeDepth(T->Rchild);
        max=hl>hr?hl:hr;
        return max+1;
    }
    else
        return 0;
}

void PreOrder(BiTree T)//  
{
    if(T!=NULL)
    {
        printf("%c ",T->data);
        PreOrder(T->Lchild);
        PreOrder(T->Rchild);
    }
}

void Destory(BiTree T)
{
    if(T!=NULL)
    {
        Destory(T->Lchild);
        Destory(T->Rchild);
        free(T);
    }
}

void Delete(BiTree T,char x)
{
    BiTNode *p=Find(T,x);
    if(p!=NULL)
        Destory(p);
}

iviewフォーム検証selectタグについてv-forを使用している間、ずっと通らない問題を検証します.