/*************************

程序名称：   最优二分检索树
作成日期：   2018/5/8
作者：     飞翔的女武神
其中树图绘制程序来源于网络

*************************/

#include<iostream>
#include<cstdio>
#include<conio.h>
#include<string>
#include<fstream>

using namespace std;

#define ForMyLove return 0

const int maxn = 2000;

double  chn[maxn];          //某元素的查找代价
double  pref[maxn];         //某段元素的查找代价之和
double  C[maxn][maxn];      //某段元素的平均查找代价
int     R[maxn][maxn];      //某段元素的根
int     tre[maxn];          //树结构

double sumft(int i, int j) {
    return pref[j] - pref[i - 1];
}

string replace(string &s) {
    string ss;
    for (int i = 0; i<s.size(); i++) {
        if (s[i] != '|')ss.append(".");
        else ss.append("|");
    }
    return ss;
}

class Node {
public:
    int  value;
    Node *left;
    Node *right;
    string s;//该节点对应的一行字符串
    int   n;//0、1、2分别代表根节点、左孩子、右孩子

    Node(int value = 0, int n = 0) {
        this->value = value;
        this->n = n;
        this->left = NULL;
        this->right = NULL;
        this->s.append(itoa(value, new char[10], 10));
    }
    void addNode(int value = 0) {
        //保证有孩子的节点对应的字符串末尾有"-|"
        if ('|' != s[s.size() - 1])s.append("-|");
        string ss;
        int index;
        //判断新节点添加到那一边
        if (value <= this->value) {
            //若没有左孩子,则添加为该节点的左孩子
            if (NULL == this->left) {
                left = new Node(value, 1);
                //新节点是父节点的左孩子，这时如果父节点也是其上一层节点的左孩子，那么把前面的都换成点，否则只把前面的数字换成点
                if (1 == this->n) {
                    ss = replace(s).substr(0, s.size() - 1);
                    index = ss.rfind("|");
                    if (index != string::npos)ss = ss.substr(0, index) + "." + ss.substr(index + 1);
                    ss.append("|-");
                }
                else {
                    ss = replace(s) + "-";
                }
                left->s.insert(0, ss);
            }
            else {
                this->left->addNode(value);
            }
        }
        else {
            //此处同上
            if (NULL == this->right) {
                right = new Node(value, 2);
                if (2 == this->n) {
                    ss = replace(s).substr(0, s.size() - 1);
                    index = ss.rfind("|");
                    if (index != string::npos)ss = ss.substr(0, index) + "." + ss.substr(index + 1);
                    ss.append("|-");
                }
                else {
                    ss = replace(s) + "-";
                }
                right->s.insert(0, ss);
            }
            else {
                right->addNode(value);
            }
        }
    }
    void print() {
        if (NULL != this->right)this->right->print();

        cout << s << endl;

        if (NULL != this->left)this->left->print();
    }
};

void bldTre(int &tag, int bg, int ed) {
    if (bg > ed) {
        return;
    }

    tre[tag++] = R[bg][ed];
    if (bg == ed) {
        return;
    }

    bldTre(tag, bg, R[bg][ed] - 1);
    bldTre(tag, R[bg][ed] + 1, ed);
}

int main() {

    /*
    //输入
    int n;
    cout << "请输入二分检索树的节点个数(<" << maxn << ")：";
    scanf("%d", &n);

    cout << "请输入每个节点被查找到的概率：";
    for (int i = 1; i <= n; i++) {
        scanf("%lf", &chn[i]);
    }
    */

    //文件读入
    int n;
    ifstream ifs;
    ifs.open("Input.txt");

    ifs >> n;
    cout << "二分检索树的节点个数：" << n << endl;
    cout << "每个节点被查找到的概率：";
    for (int i = 1; i <= n; i++) {
        ifs >> chn[i];
        cout << chn[i] << " ";
    }
    cout << endl;

    //计算前缀和
    pref[0] = 0;
    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + chn[i];
    }

    //初始化表
    for (int i = 1; i <= n; i++) {
        C[i][i - 1] = 0;
        C[i][i] = chn[i];
        R[i][i] = i;
    }
    C[n + 1][n] = 0;

    //填表的其他部分
    double minVal;
    for (int d = 1; d <= n - 1; d++) {              //某段元素的跨度

        for (int i = 1; i <= n - d; i++) {          //该段的起点

            int j = i + d;                          //该段的终点

            //更新该位置的最小值
            minVal = maxn;                          //初始化最小值
            for (int k = i; k <= j; k++) {
                if (C[i][k - 1] + C[k + 1][j] < minVal) {
                    minVal = C[i][k - 1] + C[k + 1][j];
                    R[i][j] = k;                    //更新根节点
                }
            }

            //加上该段的概率总和
            C[i][j] = minVal + sumft(i, j);

        }

    }

    //打印结果
    cout << "最优二分检索树的平均查找代价为：" << C[1][n] << endl;
    cout << "树图如下：" << endl;

    //打印树图
    int len = 0;
    bldTre(len, 1, n);

    Node node(tre[0]);
    for (int i = 1; i < len; i++) {
        node.addNode(tre[i]);
    }
    node.print();

    ForMyLove;

}
/**************************************

Input:
4
0.1 0.2 0.4 0.3

**************************************/

/**************************************

Output:

二分检索树的节点个数：4
每个节点被查找到的概率：0.1 0.2 0.4 0.3
最优二分检索树的平均查找代价为：1.7
树图如下：
..|-4
3-|
..|-2-|
......|-1

***************************************/

最优二分检索树

最优二分检索树问题：求一棵使得预期成本最小的二分检索树

一、问题引出

  或是一棵空树；或者是具有如下性质的非空二叉树：

 （1）左子树的所有结点均小于根的值；

 （2）右子树的所有结点均大于根的值；



对于一个给定的标识符集合，可能有若干棵不同的二分检索树:



不同形态的二分检索树对标识符的检索性能是不同的。

设给定的标识符集合是{a1,a2,…,an}，并假定a1＜a2＜ … ＜ an。设，P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足： ai＜X＜ai+1，0≤i≤n（设a0=-∞,an+1=+∞)时的概率，即一种不成功检索情况下的概率。



内结点：代表成功检索情况，刚好有n个

外结点：代表不成功检索情况，刚好有n＋1个

平均检索成本＝Σ每种情况出现的概率×该情况下所需的比较次数

平均检索成本的构成：成功检索成分＋不成功检索成分

       ●成功检索：在内结点终止的成功检索    P(i)*level(ai) ； 其中，level(ai)= 结点ai的级数=l

       ●不成功检索：外部结点的不成功检索的成本分担额为：Q(i)*(level(Ei)-1)

最优二分检索树问题：求一棵使得预期成本最小的二分检索树

二、问题分析

2.1、多阶段决策过程

把构造二分检索树的过程看成一系列决策的结果。

决策的策略：决策树根，如果{a1,a2,…,an}存在一棵二分检索树，ak是该树的根，则内结点a1,a2,…,ak-1和外部结点E0,E1,…,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中。



       ● 左、右子树的预期成本——左、右子树的根处于第一级

       ● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1

2.1、最优性原理成立



若T最优二分检索树，则COST(L)和COST(R)将分别是包含a1,a2,…,ak-1和E0,E1,…,Ek-1、及ak＋1, ak+2, …,an和Ek,Ek+1,…,En的最优二分检索(子)树。记由ai+1,ai+2,…,aj和Ei,Ei+!,…,Ej构成的二分检索树的成本为C(i,j)，则对于最优二分检索树T有，

                COST(L) = C(0,k-1)

                COST(R) = C(k,n)



C[i,j] 表示点i+1，i+2到点j所组成的最优解

W[i,j] 表示i-j所有节点的概率和，因为在左右子树添加一个根节点，导致左右子树的所有节点的深度增加了1，所以加上W[i,j]

三、最优检索树构建过程



四、例子

设n=4,且(a1,a2,a3,a4)=(do,if,read,while)。设P(1:4) = (3,3,1,1)，Q(0:4) = (2,3,1,1,1) (概率值“扩大”了16倍)

初始：W(i,i)=Q(i)     C(i,i)=0  R(i,i)=0

1、计算W C R

 



 

2、计算结果



3、二分检索树：

       T04=2 =>T01(左子树），T24(右子树）  即0到4以2为分界

       T01=1 =>T00(左子树），T11(右子树）

       T24=3 =>T22(左子树），T34(右子树）

4、树的形态

 



 

算法作业4 最优二分检索树的实现。


问题描述：给定n个标识符，a1<a2<……<an,已知成功检索的概率p[i],不成功检索的概率q[i]，(0<=i<=n)，构造一颗检索成本最小的二分检索树。
算法思想：采用动态规划的方法，如果ak为最优二分检索树的跟，则其左子树也是一棵最优二分检索树，同理，右子树也是一棵最优二分检索树。


记由ai+1,ai+2,…,aj和Ei,Ei+1,…,Ej构成的最优二分检索树的预期成本为C(i, j)，设二分检索树T以ak为根。则有


COST(L) = C(0,k-1)

COST(R) = C(k,n)
这里做右子树的计算COST都是以其子树的根为第一级来计算的，所以会有成本差额w(0,k)和w(k,n)
c(0,n)=min{c(0,k)+c(k+1,n)+w(0,n)}
w(0,n)=p[k]+w(0,k-1)+w(k,n).


采用向前递推过程：
首先计算所有j-i=1的c(i,j)；
然后依次计算j-i=2,3,……n的c(i,j)；
c(0,n)等于最优二分检索树的成本。
初始值c(i,i)=0,w(i,i)=q(i),0<=i<=n,
在计算C(i, j)的过程中，记下使之取得最小值的k值，即树Tij的根，记为R(i, j)。

根据R(i,j)推导树的形态。



#include <stdio.h>
#include <stdlib.h>
#include <string.h>
float *p,*q;
//float p[5]={-1,3,3,1,1};
//float q[5]={2,3,1,1,1};
float **c,**w;
int **R;
int n; 
//int n=4;
char *a[10];
//char a[4][10]={{'d','o'},{'i','f'},{'r','e','a','d'},{'w','h','i','l','e'}};
typedef struct BiTNode{
        int num;
        BiTNode* Lc;
        BiTNode* Rc;
        }BiTNode, *BiTree;
        


//录入标识符集和成功检索概率以及不成功检索概率 
void input()
{
     int i;
     printf("请输入字符个数：");
     scanf("%d",&n);
     p=(float *)malloc(sizeof(float)*(n+1));
     q=(float *)malloc(sizeof(float)*(n+1));
     
     printf("请键入字符集：\n");
     for(i=0;i<n;i++)
     {
             printf("a[%d]=",i);
             a[i]=(char *)malloc(sizeof(char)*10);
             scanf("%s",a[i]);
     }
    
     p[0]=-1;
     for(i=1;i<=n;i++)//输入各字符检索成功的概率 
     {
             printf("p[%d]=",i);           
             scanf("%f",&p[i]);
     }   
    
     for(i=0;i<=n;i++) //输入检索不成功的概率    
     {
             printf("q[%d]=",i);           
             scanf("%f",&q[i]);  
     }
}
       
void OBST( )
{

     c=(float **)malloc(sizeof(float)*(n+1));
     w=(float **)malloc(sizeof(float)*(n+1));
     R=(int **)malloc(sizeof(int)*(n+1));     
     int i,j,m,k,l;
     float tmp,tmp1;
     for(i=0;i<=n;i++)
     {
           c[i]=(float *)malloc(sizeof(float)*(n+1));
           memset(c[i],0,sizeof(float)*(n+1));
           w[i]=(float *)malloc(sizeof(float)*(n+1));
           memset(w[i],0,sizeof(float)*(n+1));
           R[i]=(int *)malloc(sizeof(int)*(n+1));
           memset(R[i],0,sizeof(int)*(n+1));
     }
     for(i=0;i<n;i++)
     {
           w[i][i]=q[i];
           c[i][i]=0;
           R[i][i]=0;
           w[i][i+1]=q[i+1]+p[i+1]+q[i];
           R[i][i+1]=i+1;
           c[i][i+1]=q[i+1]+p[i+1]+q[i];
     }
     w[n][n]=q[n];
     R[n][n]=0;
     c[n][n]=0;
     for(m=1;m<=n;m++)
     {//找有m个结点的最优树
         for(i=0;i<=n-m;i++)
         {
             j=i+m;
             w[i][j]=w[i][j-1]+q[j]+p[j];            
             tmp=c[i][i]+c[i+1][j];
             k=i+1;
             //printf("%d %d\n",R[i][j-1],R[i+1][j]);
             for(l=i+2;l<=j;l++)
             {
                  tmp1=c[i][l-1]+c[l][j];
                  if(tmp1<tmp)
                  {  
                     tmp=tmp1;
                     k=l;
                  }
             }         
             c[i][j]=w[i][j]+c[i][k-1]+c[k][j];
             R[i][j]=k;
             //printf("c[%d][%d]=%.0f R[%d][%d]=%d\t",i,j,c[i][j],i,j,R[i][j]);
         }  
        // printf("\n"); 
     }
} 
BiTree buildtree(int i,int j)
{
       if(i>=j)
          return NULL;
       BiTree Tr;
       Tr=(BiTree)malloc(sizeof(BiTNode));
       //memset(Tr,0,sizeof(BiTNode));
       if(!Tr)
          return NULL;
       Tr->num=R[i][j];
       Tr->Lc=buildtree(i,R[i][j]-1);
       Tr->Rc=buildtree(R[i][j],j);
       return Tr;
}
void preTree(BiTree T)//先序并输出 
{
     if(T)
     {
        printf("%s ",a[T->num-1]);
        //printf(" %d ",T->num);
        preTree(T->Lc);
        preTree(T->Rc);  
     } 
}
 void midTree(BiTree T)//中序并输出
 {
	if(T!=NULL)
	{
    	midTree(T->Lc);
    	printf("%s ",a[T->num-1]);
    	midTree(T->Rc);
	}
}
int main(int argc, char *argv[])
{

   BiTree BT;
   input();
   OBST();
   printf("c[0][%d]=%.2f,R[0][%d]=%d\n",n,c[0][n],n,R[0][n]);
   BT=buildtree(0,n);
   printf("先序：");
   preTree(BT);
   printf("\n");
   printf("中序：");
   midTree(BT); 
   printf("\n");  
  system("PAUSE");	
  return 0;
}

最优二分检索树
二分检索树T是一棵二元树

①T的左子树的所有元素比根结点中的元素小；
②T的右子树的所有元素比根结点中的元素大；
③T的左子树和右子树也是二分检索树。
注： 二分检索树要求树中所有结点的元素值互异


最优二分检索树问题：
求一棵预期成本最小的二分检索树
预期总的成本公式表示如下
解释：预期成本等于成功检索的所有情况和不成功检索情况乘以相应的概率。P(i)表示成功检索i的概率，Q(i)表示不成功检索i的概率


把构造二分检索树的过程看成一系列决策的结果。
–决策的策略：决策树根，如果{a1,a2,…,an}存在一棵二分检索树，ak是该树的根，则内结点a1,a2,…,ak-1和外部结点E0,E1,…,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中
若：levelT(X)为结点X在树T中的级数，level(X)为X在T的左/

右子树中的级数，则：levelT(X) = level(X)+1


 
目的是求出递推公式：
COST(T)与COST(L）和COST(R)之间的关系
把level(ai)+1分开，1单独拿出来了，剩下的就分别是左子树和右子树的成本（土黄色部分）


W[i,j] 表示i-j所有节点的概率和，包括成功检索的概率和不成功检索的概率。
所以树的最小成本可以表示成关于左右子树的最小成本的等式

解释：因为在左右子树添加一个根节点，导致左右子树的所有节点的深度增加了1，所以加上W[i,j]，这里相当于W[0,n]，
表示所有节点检索成功或者不成功的概率和。W[0,n] = P(k)+W(0,k-1)+W(k,n)。
同理，用到树的每颗子树都会成立。每科子树的最小成本设为C(i,j)，那么有



C[i,j] 表示点i+1，i+2到点j中，选择任意一个点作为根，在（j-i）个解中找出成本最小的最优解


向前递推过程：
首先计算所有j-i=1的C(i, j)
然后依次计算j-i=2,3,…,n的C(i,j)。
C(0,n)=最优二分检索树的成本。

初始值

C(i,i) = 0

W(i,i) = Q(i)，0≤i≤n
最优二分检索树的构造

在计算C(i, j)的过程中，记下使之取得最小值的k值，即树Tij的根，记为R(i, j)。

依据R(0, n)…，推导树的形态
 

#include <iostream>

using namespace std;
#define MAX 65536
#define LENGTH 64

float W[5][5] = {0};
float C[5][5] = {0};
int R[5][5] = {0};

int osbtree[LENGTH] = {0};
int index;
void OBST(float p[],float q[],int n)
{
    int i,j,k;
    float min;
    for(i=0;i<=n-1;++i)
    {
        W[i][i] = q[i];
        R[i][i] = 0;
        C[i][i] = 0;
        W[i][i+1] = W[i][i]+p[i+1]+q[i+1];
        R[i][i+1] = i+1;
        C[i][i+1] = W[i][i+1];
    }
    W[n][n] = q[n];
    R[n][n] = 0;
    C[n][n] = 0;
    //m代表目前构造的树有m个节点，
    //m从2到n个节点
    for(int m=2;m<=n;++m)
     for(i=0;i<=n-m;++i)
     {
         //每次比较必须重置min，否则根节点可能不改变
         min = MAX;
         j = i+m;
         W[i][j] = W[i][j-1]+p[j]+q[j];
         for(int l=i+1;l<=j;++l)
         {
             //
             if((C[i][l-1]+C[l][j]) < min)
             {
                min = (C[i][l-1]+C[l][j]);
                k = l;
             }
         }
         C[i][j] = W[i][j]+C[i][k-1]+C[k][j];
         R[i][j] = k;
     }
}


void PrintTree(int i,int j)
{
    if(i >= j)
        return;
    //存储根节点的标号
    osbtree[index++] = R[i][j];
    //左子树,存储输出左子树标志/
    osbtree[index++] = '/';
    PrintTree(i,R[i][j]-1);
    /*右子树,存储标志输出右子树标志\*/
    osbtree[index++] = '\\';
    PrintTree(R[i][j],j);
}

int main()
{
    char string[5][6] = {"","end","goto","print","stop"};
    //float p[5] = {0,0.05,0.2,0.1,0.05};
    //概率值扩大了20倍
    float p[5] = {0,1,4,2,1};
    //float q[5] = {0.2,0.1,0.2,0.05,0.05};
    float q[5] = {4,2,4,1,1};
    OBST(p,q,4);
    PrintTree(0,4);
    /*
    for(int i=0;i<5;++i)
    {
     for(int j=0;j<5;++j)
         //打印格式i表示行坐标，j表示列坐标
        cout<<W[j][j+i]<<","<<C[j][j+i]<<","<<R[j][j+i]<<'\t';
     cout<<endl;
    }
    */
    //打印根节点
    cout<<'\t'<<string[osbtree[0]]<<endl;
    for(int i=1;i<index;++i)
    {
        if(osbtree[i] == '/' || osbtree[i]=='\\')
            continue;
        else if(osbtree[i-1] == '/')
            cout<<string[osbtree[i]];
        else if(osbtree[i-1] == '\\')
            cout<<"\t\t"<<string[osbtree[i]]<<endl;
    }
    return 0;
}