本章作业：9.31，9.33，9.35，9.38

9.31 试编写一个判别给定二叉树是否为二叉排序树的算法, 设此二叉树以二叉链表作为存储结构,且树中节点的关键字均不同.

int IsSearchTree(const BTNode *t){
    if(!t) //空二叉树情况
        return 1;
    else if(!(t->lchild) && !(t->rchild))//左右子树都无情况
        return 1;
    else if((t->lchild) && !(t->rchild)){//只有左子树情况
        if(t->lchild->data>t->data)
            return 0;
        else
            return IsSearchTree(t->lchild);
    }
    else if((t->rchild) && !(t->lchild)){//只有右子树情况
        if(t->rchild->datadata)
            return 0;
        else
            return IsSearchTree(t->rchild);
    }
    else{ //左右子树全有情况
        if((t->lchild->data>t->data) ||(t->rchild->datadata))
            return 0;
        else
            return IsSearchTree(t->lchild) && IsSearchTree(t->rchild);
    }
}

中序遍历二叉树, 然后判断输出的中序序列是否有序.

    int pre = -99999; // 上一个访问的节点 初始化为一个最小值
    bool IsBST(BiTree T){
        if(T!=NULL){
            IsBST(T->lchild);
            int cur = T->data;
            if(currchild);
        }
        return true;
    }

9.33 编写递归算法, 从大到小输出给定二叉排序树中所有关键字不小于x的数据元素.

将中序遍历改为, 
    1) 访问右子树
    2) 访问根节点
    3) 访问左子树
当遇到一个小于x的元素时就停止输出.

    Status BstX(BiTree T){
        if(T){
            BstX(T->rchild);
            if(T->data >= x) cout << T->data << ends;
            else return;
            BstX(T->lchild);
        }
    }

9.35 假设二叉排序树以后继线索链表作存储结构, 编写输出该二叉树中所有大于 a 且小于 b 的关键字的算法.

void InOrder_Thr(BiThrTree T, int a, int b){
    P=T->lchild;
    while(P != T){
        while(p->LTag==Link) p=p->lchild;
        if(P->data >a && P->data data);
        while(p->RTag==Thread && p->rchild!=T){
            p=p->rchild;
            if(P->data >a && P->data data);            
        }
        p=p->rchild;
    }
}

9.38 编写一算法, 将两颗二叉排序树合并为一颗二叉排序树.

遍历第二棵树，把其中每个元素依次插入到第一个二叉树

void Insert_Node(Bitree &T,  BTNode *S){        //把树结点S插入到T的合适位置上
    if(S==null||T==null)   return ;       //合法性：这里不作操作
    if(S->data > T->data) {
        if(!T->rchild)  T->rchild=S;             //t右指针指向s所指结点
        else  return Insert_Node(T->rchild,S);
    }
    else if(S->data < T->data) {
        if(!T->lchild)  
            T->lchild=S;
        else 
            return  Insert_Node(T->lchild,S);
    }
    S->lchild=NULL;  //插入的新结点必须和原来的左右子树断绝关系
    S->rchild=NULL;  //否则会导致树结构的混乱
}