首页 > 其他 > 详细

二叉查找树的Insert和Delete操作

时间:2015-08-26 15:44:01      阅读:129      评论:0      收藏:0      [点我收藏+]
技术分享
struct TreeNode{
    SearchTree Left;
    SearchTree Right;
    ElementType Ele;
};
/*递归一定有出口*/
/*递归代码就是要重复使用*/
SearchTree
Insert( SearchTree T, X )
{
    /*这个是对树中没有该参数,增加节点*/
    if( T == NULL )
    {
        T = malloc( sizeof( struct TreeNode ) );
        if( T == NULL )
            fatalError();
        T->Ele = X;
        T->Left = NULL;
        T->Right = NULL:
    }
    /*继续比较*/
    else
    if(T->Ele > X )
        T->Left = Insert( T->Left, X );//对于没有左子节点,返回新建节点指针,若有,在递归返回时,则相当于什么都没做
    else
    if( T->Ele < X )
        T->Right = Insert( T->Right, X );

    return T;
}

SearchTree
FindMin(SearchTree T )
{
    if(T == NULL)
        return NULL;//只针对第一次
    if( T->Left != NULL )
        return FindMin( T->Left );
    return T;
}

//二叉查找树的删除例程
SearchTree
Delete( SearchTree T, ElementType X )
{
    S earchTree TmpCell;
    if( T == NULL )
        Error("no Element found");
    if( T->Ele > X )
        T->Left = Delete( T->Left, X );
    else if( T->Ele < X )
        Delete( T->Right, X );
    else if( T->Right && T->Left )
    {
        TmpCell = FindMin(T->Right);
        T->Ele = TmpCell->Ele;
        Delete( TmpCell, T->Ele );
    }
    else//供给1.删除只有一个或没有儿子的父节点2.删除右子树最小节点
    {
        if( T->Left == NULL )
            T = T->Right;
        else if(T->Right == NULL )
            T = T->Left;
    }
    return T;
}
View Code

 

二叉查找树的Insert和Delete操作

原文:http://www.cnblogs.com/gabygoole/p/4760231.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!