?? 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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -