【大学院受験】東北大学二叉樹関連アルゴリズム(2)

18834 ワード

アルゴリズムを作成して、与えられた二叉樹が二叉の並べ替えツリーかどうかを判断します.

keyType predt=-32767;
int JudgeBst(BiTree bt)
{
    int b1,b2;
    if(bt==null)
        return null;
    else
    {
        b1=JudegeBst(bt->lchild);
        if(bt==0||predt>=bt->data)
            return 0;
        predt=bt->data;
        b2=JudegeBst(bt->rchild);
        return b2;
    }
}

アルゴリズムを設計して、与えられた二叉樹の並べ替えツリーの中の階層を指定します.
アルゴリズムのアイデアは、二叉木を使用して、二叉の木を並べ替えると、一度検索して一つの層が落ちます.したがって、この結点を検索するのに使う回数は、この結点が二叉樹の中の階層において二叉の並べ替えツリーの非再帰的な検索アルゴリズムを採用し、nで検索レベルを保存し、一度も検索しなかった場合、nは＋1となり、対応する結点を見つけるまでになる.

int level(BiTree br,BSTNode *p)
{
    int n=0;
    Bitree t=bt;
    if(bt!=null)
    {
        n++;
        while(t->data!=p->data)
        {
            if(t->datadata)
                t=t->rchild;
            else
                t=t->rchild;
            n++;
        }
    }
    return n;
}

二叉樹が二叉樹のバランスを取るかどうかを判断するアルゴリズムを作成しました.
アルゴリズムの考え:二叉樹のバランスマークbalanceを設定して、二叉樹が平衡二叉樹であるかどうかをマークします.hは二叉樹の高さであり、順を追って巡回する再帰的アルゴリズムを採用する.①bt=nullならh=0、balance=1②btはルート結点h=1、balance=1だけです.③そうでなければ、btの左右の子樹に対して再帰演算を行い、左右の子樹の高さとバランスマークを返します.btの高さは最高子樹の高さ＋1です.左右の子樹の高さ差が1より大きいと、balance=0です.左右の子樹の高さ差が1より小さいと、左右の子樹がバランスよく、balance=1です.そうでなければ、balance=0です.

void Judege_AVL(BiTree bt, int &balance,int &h)
{
    int b1,br,h1,hr;
    if(bt==null)
    {
        h=0;balance=1;
    }
    else if(bt->lchild==null&&bt->rchild==null)
    {
        h=1;balance=1;
    }
    else
    {
        Judege_AVL(bt->lchild,b1,h1);
        Judege_AVL(bt->rchild,b2,hr);
        h=(h1>hr?h1:hr)+1;
        if(abs(h1,hr)<2)
            balance=b1&&br;
        else
            balance=0;
    }
}

アルゴリズムを設計して、与えられた二叉の並べ替えツリーの中で最小と最大のキーワードを求めます.
一本の二叉の並べ替えツリーの中で、一番左の下の結点はキーワードの最小の結点で、一番右の下の結点はキーワードの最大の結点です.

keyType Minkey(BSTNode *bt)
{   
    while(bt->lchild!=null)
        bt=bt->lchild;
    return bt->data;
}
keyType Maxkey(BSTNode *bt)
{
    while(bt->rchild!=null)
        bt=bt->rchild;
    return bt->data;
}

アルゴリズムを設計して、大きいものから小さいものまで、二叉の並べ替えツリーの中のすべての値はkのキーワードより小さいです.
アルゴリズムの考え:二叉の順序付けツリーの性質から、右のサブツリーのすべての結点値がルートの結点より大きいことが分かります.左のサブツリーのすべての結点値は、ルートの結点値よりも小さいです.大きいものから小さいものまで輸出するために、県は右の木を遍歴して、またルートを尋ねて、左の木を遍歴しました.

void OutPut(BSTNode *bt,keyType k)
{
    if(bt==null)
        return ;
    if(bt->rchild!=null)
        OutPut(bt->rchild,k);
    if(bt-=k)
        printf("%d",bt->data);
    if(bt->lchild!=null)
        OutPut(bt->lchild,k);
}

再帰的アルゴリズムを作成し、n個の結点があるランダムに確立された二叉の並べ替えツリーの中でk番目の小さい要素(1≦k≦n)を検索し、その結点を指すポインタを返します.アルゴリズムの平均時間の複雑度はO(logicaN)aで2.二叉の並べ替えツリーの各結点はdata、lchild、rchildなどのデータメンバーのほかに、countを追加します.この結点を根とする子樹上の結点個数を保存します.
アルゴリズムの考え:二叉並び替えツリーのルートノードを*tとし、結点の記憶情報に基づいて、いくつかのツリーがある場合★①1.t->lchildが空①t->rchildが空でなく、k=1であると、*tはk番目に小さい元素②t->rchildが空でなく、K!1,K番目の小さい元素が*tの右子樹★⑵t->lchildが空でない①t->lchild->count==k-1であると、*tの左子樹で*tの左子樹を検索し続ける.

BSTNode *search_Small(BSTNode *t,int k)
{
    if(k<1||k>t->data)
        return NULL;
    if(t->lchild==null)
    {
        if(k==1)
            return 1;
        else
            return search_Small(t->rchild,k-1);
    }
    else
    {
        if(t->lchild->count==k-1)
            return t;
        if(t->lchild->count>k-1)
            return search_Small(t->lchild,k);
        if(t->lchild->count1)
            return search-Small(t->lchild->count+1);
    }
}

二叉の木の中でXの結点を根の子樹の深さにすることを求めます.

int Get_Sub_Depth(BiTree T,int x)
{   
    if(T->data==x)
    {
        printf("%d",Get_Depth(T));
        exit 1;
    }
    else
    {
        if(T->lchild)
            Get_Sub_Depth(T->lchild,x);
        if(T->rchild)
            GEt_Sub_Depth(T->rchild,x);
    }
}

int GetDepth(BiTree T)
{
    if(T==null)
        return 0;
    else if(T->lchild==null&&T->rchild==null)
        retunr 1;
    else
    {
        int dep1=GetDepth(T->lchild);
        int dep2=GetDepth(T->rchild);
        if(dep1>dep2)
            return dep1+1;
        else
            return dep2+1;
    }
}

本の平衡の二叉の木を設計する各結点はすべて平衡因子bfを明示して、試しに一つの計算方法を設計して、二叉の木の高さをバランスすることを求めます.

int Heigh_bf(BiTree T)
{
    levle=-;P=T;
    while(P)
    {
        level++;
        if(p->bf<0)
            p=p->rchild;
        else
            p=p->lchild;
    }
    return level;
}

二叉樹の結点構造を二叉の平衡樹の結点構造とし、再帰的アルゴリズムを設計して、二叉樹の各結点のバランス因子を計算し、同時に二叉樹の不均衡結点個数を返します.

int GetDepth(BiTree T);
int Get_bf(BiTree T,int &count)
{   
    if(T)
    {
        Get_bf(T->lchild);
        Get_bf(T->rchild);
        m=GetDepth(T->lchild);
        n=GetDepth(T->rchild);
        T->bf=m-n;
        if(T->bf>1||T->bf1)
            count++;
    }
}

int GetDepth(BiTree T)
{
    if(T==null)
        return 0;
    else if(T->lchild==null&&T->rchild==null)
        retunr 1;
    else
    {
        int dep1=GetDepth(T->lchild);
        int dep2=GetDepth(T->rchild);
        if(dep1>dep2)
            return dep1+1;
        else
            return dep2+1;
    }
}

二叉樹の順序記憶構造が知られています.二叉リンク構造を構築します.

bool CreatrBiTree_SqlList(BiTree &T,SqList sa)
{
    BiTree ptr[sa.last+1];                sa          
    if(!sa.last)
    {
        T=null;
        return true;
    }
    ptr[1]=(BTNode *)malloc(sizeof(BTNode));
    ptr[1]->data=sa.elem[1];               
    T=Ptr[1];
    for(i=2;i<=sa.last;i++)
    {
        if(!sa.elem[i])
            return false;
        ptr[i]=(BTNode *)malloc(sizeof(BTNode));
        Ptr[i]->data=sa.elem[i];
        j=i/2;                              
        if(i-j*2)                    i j    
            ptr[j]->lchild=ptr[i];
    }
    return true;
}

二つの要素演算子だけを含む演算式を、二叉の連鎖表形式で二叉のツリーTに格納すると仮定し、設計アルゴリズムの後、順次計算式の値を巡回します.

float PostValue(BiTree T)
{
    float lv,rv;
    if(T)
    {
        lv=PostValue(T->lchild);
        rv=PostValue(T->rchild);
        seitch(T->optr)
        {
            case '+': value=lv+rv;break;
            case '-': value=lv-rv;break;
            case '*': value=lv*rv;break;
            case '/': value=lv/rv;break;
        }
        return value;
    }
}

設計アルゴリズムは、葉の結点の中空ポインタ領域を利用して、すべての葉っぱの結点を一つの率先指針として連結し、アルゴリズムは、頭の結点のアドレスを返します.

void CreateLeafList（BiTree T）
{
    if(T)
    {
        CreateLeafList(T->lchild);
        if(!T->lchild&&!T->rchild)
            if(!L)
            {
                L=(BiTree)malloc(sizeof(BNode));
                L->lchild=null;
                L->rchild=T;
                T->lchild=L;
                pre=T;
            }
            else
            {
                Pre->rchild=T;
                T->lchild=Pre;
                Pre=T;
            }
            CreateLeafList(T->rchild);
            Pre->rchild=null;
    }
}

中間順序スレッド二叉ツリーの結点構造を与え、スタックまたは再帰を使用しない場合は、最初に順方向スレッド二叉ツリーを巡回するアルゴリズム(先頭ノード)を作成してみよう.

void PreOrder_InThread(BiThrTree T)
{
    P=T->lchild;
    while(P)
    {
        while(p->ltag=0)
        {
            printf(p->data);
            p=p->lchild;
        }
        printf(p->data);
        while(p->rtag==1&&p->rchild!=T)
            p=p->rchild;
        if(p->rchild!=T)
            p=p->rchild;
    }
}

再帰せずに、スタックの中を使わずに、両親の針を持つ三叉チェーンの二叉の木を巡回します.
三叉チェーン表の二叉樹は別の主なチェーン式記憶構造である.三叉チェーンの主な違いは、その結点が二叉チェーンの結点より一つ多いのです.このドメインは、この結点両親のポインタを指す領域を記憶するために使われています.

typedef struct
{
    int data;
    PBTNode *lchild;
    PBTNode *rchild;
    PBTNode *parent;
}PBTNode,*PBiTree;

void InOrder Norecurive(PBiTree T)
{
    P=T;
    while(P->lchild)
        p=p->lchild;
    while(p)
    {
        visit(p);
        if(p->rchild)
        {
            p=p->rchild;
            while(p->lchild)
                p=p->lchild;
        }
        else if(p->parent->lchild==p)
        {
            p=p->parent;
        }
        else
        {
            p=p->parent;
            while(p->parent=&&p->parent->rchild==p)
                p=p->parent;
            p=p->parent;
        }
    }
}

アルゴリズム→並べ替えの挿入

k-meansアルゴリズムの簡単な実装