6.65.txt

数据结构实验 如下： Status Fibonacci(int k, int m, int &f) /* 求k阶斐波那契序列的第m项的值f */

void BuildBiTree(BiTree &bt, int ps, char *pre, 
                             int is, char *ino, int n)
/* 当前要建立的子树bt的元素总数为n，*/
/* 元素在前序序列pre的起始位置为ps，*/
/* 元素在中序序列ino的起始位置为is  */
{
    int left_len,right_len,i;
    if(n==0) {
        bt=NULL;
        return;
    }
    
    bt=(BiTNode*)malloc(sizeof(BiTNode));
    bt->data=pre[ps];
    for(i=is;ino[i]!=bt->data;i++);
    //注意相对位置，计数时也需要注意
    left_len=i-is;
    right_len=n-1+is-i;
    
    //左右子树
    if(left_len){
        BuildBiTree(bt->lchild,ps+1,pre,is,ino,left_len);
    }
    if(right_len>0){
        BuildBiTree(bt->rchild,n-right_len+ps,pre,n-right_len+is,ino,right_len);
    }
}