bintree.c

操作系统中的一个例子

        }
        else
        {
            pMaxNode->pParent->pRight = pMaxNode->pLeft;          
            if ( pMaxNode->pLeft != NULL )
            {
                pMaxNode->pLeft->pParent = pMaxNode->pParent;
            }
        }
        free(pMaxNode);

        return CAPI_SUCCESS;
    }

    /* 处理最多只有一个子节点的情况 */
    if ( pNode->pLeft != NULL )
    {
        pMaxNode = pNode->pLeft;
    }
    else
    {
        pMaxNode = pNode->pRight;
    }

    if ( pNode == pBinTree->pRoot )
    {
        pBinTree->pRoot = pMaxNode;
        if ( pMaxNode != NULL )
        {
            pMaxNode->pParent = NULL;
        }
    }
    else
    {
        if ( pNode->pParent->pLeft == pNode )
        {
            pNode->pParent->pLeft = pMaxNode;
        }
        else
        {
            pNode->pParent->pRight = pMaxNode;
        }
        if ( pMaxNode != NULL )
        {
            pMaxNode->pParent = pNode->pParent;
        }
    }
    if ( DestroyFunc != NULL && pNode->pData != NULL )
    {
        (*DestroyFunc)(pNode->pData);
    }
    free( pNode );

    return CAPI_SUCCESS;
}


/**	二叉排序树的左旋操作函数

	@param	BINTREEBASENODE *pANode - 要旋转的基节点	
	@param	BINTREEBASENODE **ppRoot - 二叉排序树的根节点	
	@return	void - 无	
*/
void BinTree_RotateLeft(BINTREEBASENODE *pANode, BINTREEBASENODE **ppRoot )
{
    BINTREEBASENODE  *pBNode; /* B节点指针 */
    
    pBNode = pANode->pRight;
    
    /* 将B节点的左节点变成A节点的右节点 */
    pANode->pRight = pBNode->pLeft;
    if ( pBNode->pLeft != NULL )
    {
        pBNode->pLeft->pParent = pANode;
    }
    
    /* 修改A节点的父指针和B节点的关系 */
    pBNode->pParent = pANode->pParent;
    if ( pANode == *ppRoot )
    {
        *ppRoot = pBNode;
    }
    else if ( pANode == pANode->pParent->pLeft )
    {
        pANode->pParent->pLeft = pBNode;
    }
    else
    {
        pANode->pParent->pRight = pBNode;
    }
    
    /* 将A节点变成B节点的左节点 */
    pBNode->pLeft = pANode;
    pANode->pParent = pBNode;
}


/**	二叉排序树的右旋操作函数

	@param	BINTREEBASENODE *pANode - 要旋转的基节点	
	@param	BINTREEBASENODE **ppRoot - 二叉排序树的根节点	
	@return	void - 无	
*/
void BinTree_RotateRight(BINTREEBASENODE *pANode, BINTREEBASENODE **ppRoot)
{
    BINTREEBASENODE  *pBNode; /* B节点指针 */
    
    pBNode = pANode->pLeft;
    
    /* 将B节点的右节点变成A节点的左节点 */
    pANode->pLeft = pBNode->pRight;
    if ( pBNode->pRight != NULL )
    {
        pBNode->pRight->pParent = pANode;
    }
    
    /* 修改A节点的父指针和B节点的关系 */
    pBNode->pParent = pANode->pParent;
    if ( pANode == *ppRoot )
    {
        *ppRoot = pBNode;
    }
    else if ( pANode == pANode->pParent->pRight )
    {
        pANode->pParent->pRight = pBNode;
    }
    else
    {
        pANode->pParent->pLeft = pBNode;
    }
    
    /* 将A节点变成B节点的左节点 */
    pBNode->pRight = pANode;
    pANode->pParent = pBNode;
}

/**	二叉搜索树的校验父节点链接函数

	@param	BINTREEBASENODE *pRootNode - 根节点指针	
	@return	void - 无	
*/
void BinTree_CheckParent(BINTREEBASENODE *pRootNode)
{
    BINTREEBASENODE *pNode = pRootNode;

    if ( pNode == NULL )
    {
        return;
    }

    if ( pNode->pLeft != NULL )
    {
        if ( pNode->pLeft->pParent != pNode )
        {
            printf( "%s Node's Parent is no correct!!!\n", (char *)(pNode->pLeft->pData) );
        }
        BinTree_CheckParent(pNode->pLeft);
    }

    if ( pNode->pRight != NULL )
    {
        if ( pNode->pRight->pParent != pNode )
        {
            printf( "%s Node's Parent is no correct!!!\n", (char *)(pNode->pRight->pData) );
        }
        BinTree_CheckParent(pNode->pRight);
    }
}

/**	二叉排序树的插入操作函数

	@param	BINTREEBASENODE **pRoot - 指向根节点指针的指针	
	@param	void *pData - 要插入的数据指针	
	@param	COMPAREFUNC CompareFunc - 数据比较函数	
	@param	INT nMagic - 魔法值，由调用者决定	
	@return	INT - CAPI_FAILED表示插入失败，CAPI_SUCCESS表示成功	
*/
INT BinTree_Insert(BINTREEBASENODE **pRoot, void *pData, COMPAREFUNC CompareFunc, INT nMagic)
{
    BINTREEBASENODE *pNode;
    BINTREEBASENODE *pNewNode;
    INT         nRet = 0;
    
    if ( pData == NULL || CompareFunc == NULL )
    {
        return CAPI_FAILED;
    }
    
    pNode = *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;
    pNewNode->nMagic = nMagic;
    
    if ( pNode == NULL )
    {
        *pRoot = pNewNode;
        pNewNode->pParent = NULL;
    }
    else 
    {
        if ( nRet < 0 )
        {
            pNode->pRight = pNewNode;
        }
        else
        {
            pNode->pLeft = pNewNode;
        }
        pNewNode->pParent = pNode;
    }
    
    return CAPI_SUCCESS;
}


/**	二叉树的前序遍历函数

	@param	BINTREE *pTree - 要操作的二叉树	
	@param	VISITFUNC VisitFunc - 节点访问回调函数	
	@return	void - 无	
*/
void BinTree_PreOrderTraverse(BINTREE *pTree, VISITFUNC VisitFunc)
{
    BINTREEBASENODE *pCursor;
    
    pCursor = pTree->pRoot;
    if ( pCursor == NULL )
    {
        return;
    }
    (*VisitFunc)(pCursor->pData);
    
    while ( pCursor->pLeft != NULL )
    {
        pCursor = pCursor->pLeft;
        (*VisitFunc)(pCursor->pData);
    }
    
    while ( pCursor != NULL )
    {      
        if ( pCursor->pRight != NULL )
        {
            pCursor = pCursor->pRight;
            (*VisitFunc)(pCursor->pData);
            while ( pCursor->pLeft != NULL )
            {
                pCursor = pCursor->pLeft;
                (*VisitFunc)(pCursor->pData);
            }
        }
        else
        {
            /* 回溯到父节点 */
            BINTREEBASENODE *pParent = pCursor->pParent;
            while ( pParent != NULL && pParent->pRight == pCursor )
            {
                pCursor = pParent;
                pParent = pParent->pParent;
            }
            pCursor = pParent;
        }
    }
}


/**	二叉树的中序遍历函数

	@param	BINTREE *pTree - 要操作的二叉树	
	@param	VISITFUNC VisitFunc - 节点访问回调函数	
	@return	void - 无	
*/
void BinTree_InOrderTraverse(BINTREE *pTree, VISITFUNC VisitFunc)
{
    BINTREEBASENODE *pCursor;
    void        *pData;
    
    pCursor = pTree->pRoot;
    if ( pCursor == NULL )
    {
        return;
    }
    while ( pCursor->pLeft != NULL )
    {
        pCursor = pCursor->pLeft;
    }

    while ( pCursor != NULL )
    {
        pData = pCursor->pData;
        (*VisitFunc)(pData);
    
        if ( pCursor->pRight != NULL )
        {
            pCursor = pCursor->pRight;
            while ( pCursor->pLeft != NULL )
            {
                pCursor = pCursor->pLeft;
            }
        }
        else
        {
            /* 回溯到父节点 */
            BINTREEBASENODE *pParent = pCursor->pParent;
            while ( pParent != NULL && pParent->pRight == pCursor )
            {
                pCursor = pParent;
                pParent = pParent->pParent;
            }
            pCursor = pParent;
        }
    }
}


/**	二叉树的后序遍历函数

	@param	BINTREE *pTree - 要操作的二叉树	
	@param	VISITFUNC VisitFunc - 节点访问回调函数	
	@return	void - 无	
*/
void BinTree_PostOrderTraverse(BINTREE *pTree, VISITFUNC VisitFunc)
{
    BINTREEBASENODE *pCursor;
    
    pCursor = pTree->pRoot;
    if ( pCursor == NULL )
    {
        return;
    }
    
    while ( pCursor->pLeft != NULL )
    {
        pCursor = pCursor->pLeft;
    }
    
    while ( pCursor != NULL )
    {      
        if ( pCursor->pRight != NULL )
        {
            pCursor = pCursor->pRight;
            while ( pCursor->pLeft != NULL )
            {
                pCursor = pCursor->pLeft;
            }
        }
        else
        {

            /* 回溯到父节点 */
            BINTREEBASENODE *pParent = pCursor->pParent;               
            
            (*VisitFunc)(pCursor->pData);

            while ( pParent != NULL && pParent->pRight == pCursor )
            {
                pCursor = pParent;
                pParent = pParent->pParent;

                (*VisitFunc)(pCursor->pData);
            }
            pCursor = pParent;
        }
    }
}