2013-941

2013-941

(1).找出二叉树先根序列的最后一个结点

• 二叉查找树由3个域构成
• key：给出结点数据项的值，为正整数
• left：结点的左子结点地址
• right：结点的右子结点地址
• 根结点地址为root
• 不能使用递归
• 不能使用栈

void last(BiTree root){
    BiTree *p = root;
    while(p -> right != NULL || p -> left != NULL){
       if(p -> right){
           while(p -> right != NULL){
               p = p -> right;
           }
       }else{
           p = p -> left;
       }
    }
    return p;
}

(2)将key域的值大于等于给定x的值的结点全部删除

void Del(BiTree T){//递归删除树算法
    if(T != NULL){
        Del(T -> left);
        Del(T -> right);
        free(T);
    }
}
void DeleteX(BiTree root,int x){
    BiTree Queue[MaxSize];
    int rear = -1,front = -1;
    BiTree *p = root;
    BiTree *pre = NULL;
    while(p -> right != NULL && p -> key <= x){
        pre = p;
        p = p -> right;
    }
    if(p -> key <= x){
            return;
    }
    Queue[++rear] = p;
    while(rear != front){
        p = Queue[++front];
        if(p -> key > x){
            Queue[++rear] = p -> left;
            pre -> right = p -> left;
            p -> left = NULL;
            Del(p);
        }else{
            Queue[++rear] = p -> right;
        }
    }
}