セカンダリツリー

秩序シーケンスの検索では、各要素の検索確率が同じであれば、二分検索が最も速い検索アルゴリズムであるが、検索要素の検索確率が異なる場合、二分検索で最も速い検索方法とは限らず、ASLを計算することで知ることができる.
従って、このような要素探索確率が等しくない秩序配列に基づいて、最適なツリーを構築する方法により、このツリーの重み付き経路長を最小にすることができ、このようなツリーの構造コストは非常に大きいので、近似アルゴリズムを用いて、優先的なツリーを構築し、このツリーの重み付き経路長がほぼ最小に達する.
優先検索数のアルゴリズムは以下のように記述される.
次は二次優二叉木構造のアルゴリズムです

#include <iostream>
#include <cmath>
using namespace std;

typedef struct treenode
{
	char data;
    int weight;
    treenode *left;
    treenode *right;
}Treenode,*Treep;

//      
void init_tree(Treep &root)
{
    root=NULL;
    cout<<"     !"<<endl;
}

//     
void SecondOptimal(Treep &rt, char R[],int sw[], int low, int high)
{
    //    R[low....high]       sw(  sw[0]==0)         T
    int i=low;
    int min = fabs(sw[high] - sw[low]);
    int dw = sw[high] + sw[low-1];
    for(int j=low+1; j<=high; ++j)        //     ΔPi 
    {
        if(fabs(dw-sw[j]-sw[j-1]) < min)
        {
            i=j;
            min=fabs(dw-sw[j]-sw[j-1]);
        }
    }
    rt=new Treenode;
    rt->data=R[i];        //    
    if(i==low)            //     
        rt->left = NULL;
    else                //     
        SecondOptimal(rt->left, R, sw, low, i-1);

    if(i==high)            //     
        rt->right = NULL;
    else                //     
        SecondOptimal(rt->right, R, sw, i+1, high);
}//SecondOptimal

//       
void pre_order(Treep rt)
{
    if(rt)
    {
        cout<<rt->data<<"  ";
        pre_order(rt->left);
        pre_order(rt->right);
    }
}

//       
void in_order(Treep rt)
{
	if(rt)
	{
		in_order(rt->left);
		cout<<rt->data<<"  ";
		in_order(rt->right);
	}
}

//       
void post_order(Treep rt)
{
	if(rt)
	{
		post_order(rt->left);
		post_order(rt->right);
		cout<<rt->data<<"  ";
	}
}

//             
int seach_tree(Treep &rt,char key)
{
    if(rt==NULL) 
        return 0; 
    else 
    { 
        if(rt->data==key) 
        {
            return 1;
        }
        else
        {
            if(seach_tree(rt->left,key) || seach_tree(rt->right,key))
                return 1;    //            ，   1
            else
                return 0;    //            ，  0
        }
    }
}

#include "tree.h"
#include <iomanip>
#include <iostream>
using namespace std;

int main()
{
    Treep root;
    init_tree(root);        //    
	int low=1,high=10;
	int *weight,*sw;
	char *R;
    
	R=new char[high];
    for(int i=low; i<high; i++)
        R[i]='A'+i-1;
    cout<<"         R[]:"<<endl;
    for(i=low; i<high; i++)
        cout<<setw(3)<<R[i]<<"  ";
    cout<<endl;
    
    weight=new int[high];
    weight[0]=0;
    weight[1]=1;
    weight[2]=1;
    weight[3]=2;
    weight[4]=5;
    weight[5]=3;
    weight[6]=4;
    weight[7]=4;
    weight[8]=3;
    weight[9]=5;
    cout<<"            weight[]:"<<endl;
    for(i=low; i<high; i++)
        cout<<setw(3)<<weight[i]<<"  ";
    cout<<endl;
    	
    sw=new int[high];
    sw[0]=0;
    for(i=low; i<high; i++)
    {
        sw[i]=sw[i-1]+weight[i];
    }
    cout<<"             sw[]:"<<endl;
    for(i=low; i<high; i++)
        cout<<setw(3)<<sw[i]<<"  ";
    cout<<endl;
		
    //     
    SecondOptimal(root, R, sw, low, high-1);
	
    cout<<"       :"<<endl;
    pre_order(root);
    cout<<endl;
	
    cout<<"       :"<<endl;
    in_order(root);
    cout<<endl;

	cout<<"       :"<<endl;
    post_order(root);
    cout<<endl;

    //             
    cout<<"        !"<<endl;
    char ch;
    cin>>ch;
    if(seach_tree(root,ch)==1)
        cout<<"yes!"<<endl;
    else
        cout<<"no!"<<endl;
	
    return 0;
}

実行結果

     !
         R[]:
  A    B    C    D    E    F    G    H    I
            weight[]:
  1    1    2    5    3    4    4    3    5
             sw[]:
  1    2    4    9   12   16   20   23   28
       :
F  D  B  A  C  E  H  G  I
       :
A  B  C  D  E  F  G  H  I
       :
A  C  B  E  D  G  I  H  F
        !
F
yes!
Press any key to continue