bintree.c

操作系统中的一个例子

/*
 * Copyright (c) 2000-2008
 * Author: Weiming Zhou
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  
 */

#include <stdio.h>
#include <stdlib.h>
#include "CapiGlobal.h"
#include "BinTree.h"

/**	二叉搜索树的创建函数

	@param	void - 无	
	@return	BINTREE * -成功返回创建的二叉树指针，失败返回NULL。	
*/
BINTREE *BinTree_Create(void)
{
    BINTREE *pBinTree;

    pBinTree = (BINTREE *)malloc(sizeof(BINTREE));
    if ( pBinTree != NULL )
    {
        pBinTree->pRoot = NULL;
        pBinTree->uNodeCount = 0;
    }
    return pBinTree;
}

/**	二叉搜索树子树释放函数

	@param	BINTREEBASENODE *pRoot -子树根节点指针	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	void - 无	
*/
void BinTreeBaseNode_Destroy(BINTREEBASENODE *pRoot, 
                             DESTROYFUNC DestroyFunc)
{
    if ( pRoot != NULL )
    {
        if ( pRoot->pLeft != NULL )
        {
            BinTreeBaseNode_Destroy(pRoot->pLeft, DestroyFunc);
        }
        if ( pRoot->pRight != NULL )
        {
            BinTreeBaseNode_Destroy(pRoot->pRight, DestroyFunc);
        }
        if ( DestroyFunc != NULL && pRoot->pData != NULL )
        {
            (*DestroyFunc)(pRoot->pData);
        }
        free(pRoot);
    }
}

/**	二叉搜索树释放函数

	@param	BINTREE *pBinTree - 二叉搜索树指针	
	@param	DESTROYFUNC DestroyFunc - 数据释放回调函数	
	@return	void - 无	
*/
void BinTree_Destroy(BINTREE *pBinTree, DESTROYFUNC DestroyFunc)
{
    if ( pBinTree == NULL )
    {
        return;
    }
    BinTreeBaseNode_Destroy(pBinTree->pRoot, DestroyFunc);
    free( pBinTree );
}

/**	二叉搜索树增加节点函数，将指定数据插入到二叉树中

	@param	BINTREE *pBinTree - 二叉搜索树指针	
	@param	void *pData - 要增加的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@return	INT - CAPI_SUCCESS表示成功，CAPI_FAILED表示失败。	
*/
INT BinTree_Add(BINTREE *pBinTree, void *pData, COMPAREFUNC CompareFunc)
{
    BINTREEBASENODE *pNode;
    BINTREEBASENODE *pNewNode;
    INT         nRet = 0;

    if ( pBinTree == NULL || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }

    pNode = pBinTree->pRoot;

    while ( pNode != NULL )
    {
        nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            if ( pNode->pRight != NULL )
            {
                pNode = pNode->pRight;
                continue;
            }
        }
        else 
        {
            if ( pNode->pLeft != NULL )
            {
                pNode = pNode->pLeft;
                continue;
            }
        }
        break;
    }

    pNewNode = (BINTREEBASENODE *)malloc(sizeof(BINTREEBASENODE));
    if ( pNewNode == NULL )
    {
        return CAPI_FAILED;
    }
    pNewNode->pLeft = NULL;
    pNewNode->pRight = NULL;
    pNewNode->pData = pData;

    if ( pNode == NULL )
    {
        pBinTree->pRoot = pNewNode;
    }
    else 
    {
        if ( nRet < 0 )
        {
            pNode->pRight = pNewNode;
        }
        else
        {
            pNode->pLeft = pNewNode;
        }
    }
    pBinTree->uNodeCount += 1;
        
    return CAPI_SUCCESS;
}



/**	二叉搜索树的查找函数

	@param	BINTREEBASENODE *pRoot - 二叉搜索树的根节点指针	
	@param	void *pData - 要查找的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	void * - 成功返回查找到的数据，失败返回NULL。	
*/
void *BinTree_Find(BINTREEBASENODE *pRoot, void *pData, COMPAREFUNC CompareFunc)
{
    BINTREEBASENODE *pNode;
    
    pNode = pRoot;
    
    while ( pNode != NULL )
    {
        INT nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            return pNode->pData;
        }
    }
    return NULL;
}


/**	二叉树查找函数

	@param	BINTREEBASENODE *pRoot - 根节点指针	
	@param	void *pData - 数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@return	BINTREEBASENODE * - 根节点指针	
*/
BINTREEBASENODE *BinTree_FindNode(BINTREEBASENODE *pRoot, 
                              void *pData, COMPAREFUNC CompareFunc)
{
    BINTREEBASENODE *pNode;
    
    pNode = pRoot;
    
    while ( pNode != NULL )
    {
        INT nRet = (*CompareFunc)(pNode->pData, pData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            return pNode;
        }
    }
    return NULL;
}

/**	二叉搜索树的添加节点到指定节点的左子树的函数

	@param	BINTREE *pBinTree - 二叉搜索树指针	
	@param	void *pTagNodeData - 指定节点指针	
	@param	void *pData - 要添加的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@return	INT - CAPI_SUCCESS表示成功，CAPI_FAILED表示失败。	
*/
INT BinTree_AddLeft(BINTREE *pBinTree, void *pTagNodeData, 
                    void *pData, COMPAREFUNC CompareFunc)
{
    BINTREEBASENODE *pNode;
    INT         nRet;

    if ( pBinTree == NULL || pTagNodeData == NULL 
        || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    /* 查找要插入的节点 */
    pNode = pBinTree->pRoot;
    while ( pNode != NULL )
    {
        nRet = (*CompareFunc)(pNode->pData, pTagNodeData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            break;
        }
    }
    if ( pNode != NULL )
    {
        /* 
         *  找到了要插入的目标节点，生成新节点插入作为其左子树
         * 如果原来有左子树则将新节点左子树指针指向它
         */
        BINTREEBASENODE *pNewNode;
        pNewNode = (BINTREEBASENODE *)malloc(sizeof(BINTREEBASENODE));
        if ( pNewNode != NULL )
        {
            pNewNode->pData = pData;
            pNewNode->pLeft = pNode->pLeft;
            pNewNode->pRight = NULL;
            pNode->pLeft = pNewNode;
            return CAPI_SUCCESS;
        }
    }
    return CAPI_FAILED;
}

/**	二叉搜索树的添加节点到指定节点的右子树的函数

	@param	BINTREE *pBinTree - 二叉搜索树指针	
	@param	void *pTagNodeData - 指定节点指针	
	@param	void *pData - 数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较回调函数	
	@return	INT - CAPI_SUCCESS表示成功，CAPI_FAILED表示失败。	
*/
INT BinTree_AddRight(BINTREE *pBinTree, void *pTagNodeData, 
                    void *pData, COMPAREFUNC CompareFunc)
{
    BINTREEBASENODE *pNode;
    INT         nRet;

    if ( pBinTree == NULL || pTagNodeData == NULL 
        || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    /* 查找要插入的节点 */
    pNode = pBinTree->pRoot;
    while ( pNode != NULL )
    {
        nRet = (*CompareFunc)(pNode->pData, pTagNodeData);
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            break;
        }
    }
    if ( pNode != NULL )
    {
        /* 
         *  找到了要插入的目标节点，生成新节点插入作为其左子树
         * 如果原来有左子树则将新节点左子树指针指向它
         */
        BINTREEBASENODE *pNewNode;
        pNewNode = (BINTREEBASENODE *)malloc(sizeof(BINTREEBASENODE));
        if ( pNewNode != NULL )
        {
            pNewNode->pData = pData;
            pNewNode->pLeft = NULL;
            pNewNode->pRight = pNode->pRight;
            pNode->pRight = pNewNode;
            return CAPI_SUCCESS;
        }
    }
    return CAPI_FAILED;
}

/**	二叉搜索树的删除函数

	@param	BINTREE *pBinTree - 二叉树指针	
	@param	void *pData - 要删除的数据指针	
	@param	COMPAREFUNC  CompareFunc - 数据比较回调函数	
	@param	DESTROYFUNC  DestroyFunc - 数据释放回调函数	
	@return	INT - CAPI_FAILED表示失败，CAPI_SUCCESS表示成功	
*/
INT BinTree_Delete(BINTREE *pBinTree, void *pData, 
                   COMPAREFUNC  CompareFunc,
                   DESTROYFUNC  DestroyFunc)
{
    BINTREEBASENODE *pNode;
    BINTREEBASENODE *pMaxNode;
    INT         nRet;

    if ( pBinTree == NULL ||pBinTree->pRoot == NULL
        || pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    pNode = pBinTree->pRoot;
    while ( pNode != NULL )
    {
        nRet = (*CompareFunc)(pNode->pData, pData); 
        if ( nRet < 0 )
        {
            pNode = pNode->pRight;
        }
        else if ( nRet > 0 )
        {
            pNode = pNode->pLeft;
        }
        else
        {
            break;
        }
    }

    if ( pNode == NULL )
    {
        /* 未找到指定节点 */
        return CAPI_FAILED;
    }

    /* 处理查找到的pNode有两个子节点的情况 */
    if ( pNode->pLeft != NULL && pNode->pRight != NULL )
    {
        pMaxNode = pNode->pLeft;
        while ( pMaxNode->pRight != NULL )
        {
            pMaxNode = pMaxNode->pRight;
        }
        if ( DestroyFunc != NULL && pNode->pData != NULL )
        {
            (*DestroyFunc)(pNode->pData);
        }
        pNode->pData = pMaxNode->pData;
        if ( pMaxNode == pNode->pLeft )
        {
            pNode->pLeft = pMaxNode->pLeft;
            if ( pMaxNode->pLeft != NULL )
            {
                pMaxNode->pLeft->pParent = pNode;
            }