#include<bits/stdc++.h>
#define maxsize 100
using namespace std;
typedef struct treenode
{//定义二叉树结构
    char data;
    struct node *lchild,*rchild;
}*bitree,bitnode;

//查找1
bitnode find( int x, bitree bst ) {
    if( !bst ) 
        return null; /*查找失败*/ 
    if( x > bst->data ) 
        return find( x, bst->rchild ); /*在右子树中继续查找*/
    else if( x < bst->data ) 
        return find( x, bst->lchild ); /*在左子树中继续查找*/
    else /* x == bst->data */ 
        return bst; /*查找成功,返回结点的找到结点的地址*/
}
//查找2(非递归)
bitnode iterfind( int x, bitree bst ) {
    while( bst ) { 
        if( x > bst->data ) bst = bst->rchild; /*向右子树中移动,继续查找*/
        else if( x < bst->data ) 
            bst = bst->lchild; /*向左子树中移动,继续查找*/
        else /* x == bst->data */ 
            return bst; /*查找成功,返回结点的找到结点的地址*/
    } 
    return null; /*查找失败*/ 
}

//查最小(递归)
bitnode findmin(bitree bst){
    if(!bst)
        return null;
    else if(!bst->lchild)
        return bst;
    else
        return findmin(bst->lchild);
}
//查最大(迭代)
bitnode findmax(bitree bst){
    if(bst)
        while(bst->rchild)
            bst = bst->rchild;
    return bst;
}
//插入
bitree insert( int x, bitree bst ) {
    if( !bst ){
        /*若原树为空,生成并返回一个结点的二叉搜索树*/
        bst = malloc(sizeof(struct treenode)); 
        bst->data = x; 
        bst->lchild = bst->rchild = null;
    }else /*开始找要插入元素的位置*/ 
        if( x < bst->data ) 
            bst->lchild = insert( x, bst->lchild); 
        /*递归插入左子树*/
        else if( x > bst->data ) 
            bst->rchild = insert( x, bst->rchild); /*递归插入右子树*/
        /* else x已经存在,什么都不做 */ 
    return bst; 
}
//删除
bitree delete( int x, bitree bst ) {
    bitnode tmp; 
    if( !bst ) printf("要删除的元素未找到"); 
    else if( x < bst->data )
        bst->lchild = delete( x, bst->lchild); /* 左子树递归删除 */
    else if( x > bst->data ) 
        bst->rchild = delete( x, bst->rchild); /* 右子树递归删除 */
    else /*找到要删除的结点 */ 
        if( bst->lchild && bst->rchild ) { /*被删除结点有左右两个子结点 */ 
            tmp = findmin( bst->rchild );
            /*在右子树中找最小的元素填充删除结点*/
            bst->data = tmp->data; 
            bst->rchild = delete( bst->data, bst->rchild); 
            /*在删除结点的右子树中删除最小元素*/
        } else { /*被删除结点有一个或无子结点*/ 
            tmp = bst;
            if( !bst->lchild ) /* 有右孩子或无子结点*/ 
                bst = bst->rchild;
            else if( !bst->rchild ) /*有左孩子或无子结点*/ 
                bst = bst->lchild;
            free( tmp );
        }
    return bst;
}
分类: 未分类

0 条评论

发表回复

Avatar placeholder

您的邮箱地址不会被公开。 必填项已用 * 标注