排序二叉树 SortBinaryTree

排序二叉树 SortBinaryTree

排序二叉树是比较基本但是重要的算法,它在许多实际编码中都不可缺少，还有不少算法和数据结构都基于此。比如，二叉查找树，平衡二叉树，红黑树等等。

SortBinaryTree的源代码见: https://github.com/duankai/SortBinaryTree/

下面，介绍SortBinaryTree。

1. SortBinaryTree的节点结构：

struct TREE_NODE_T 
{ 
    AnyType * pcData; 
    TREE_NODE_T<AnyType> * pstParent; 
    TREE_NODE_T<AnyType> * pstLeftChild; 
    TREE_NODE_T<AnyType> * pstRightChild; 
};

2. 构造函数

SortBinaryTree(int(* cmpFunc)(AnyType * d1, AnyType * d2))
{
        m_pstRoot         = NULL;
m_pstSmallestNode = NULL;
m_cmpFunc         = cmpFunc;
};

其中，cmpFunc是AnyData的比较函数。

3. 树的插入

树的插入采用递归的方法，首先寻找插入节点的合适位置，然后插入。

bool InsertTreeNode(TREE_NODE_T<AnyType> * pstNode, TREE_NODE_T<AnyType> * pstTempRoot)
{
if (!pstNode)
{
return false;
}

if (NULL != pstTempRoot)
{
if (m_cmpFunc(pstNode->pcData ,pstTempRoot->pcData) > 0)
{
if (NULL != pstTempRoot->pstRightChild)
{
return InsertTreeNode(pstNode, pstTempRoot->pstRightChild);
}
else
{
pstTempRoot->pstRightChild = pstNode;
pstNode->pstParent = pstTempRoot;
}
}
if (m_cmpFunc(pstNode->pcData ,pstTempRoot->pcData) < 0)
{
if (NULL != pstTempRoot->pstLeftChild)
{
return InsertTreeNode(pstNode, pstTempRoot->pstLeftChild);
}
else
{
pstTempRoot->pstLeftChild = pstNode;
pstNode->pstParent = pstTempRoot;
}
}
if (m_cmpFunc(pstNode->pcData ,pstTempRoot->pcData) == 0)
{
return false;
}
}
else
{
m_pstRoot = pstNode;
}
return true;
};

4. 查找

    TREE_NODE_T<AnyType> * SearchNode(void * pvData, TREE_NODE_T<AnyType> * pstRoot)
    {
        if (NULL == pstRoot || NULL == pvData)
        {
            return NULL;
        }

        if (m_cmpFunc(pstRoot->pcData ,(AnyType *)pvData) == 0)
        {
            return pstRoot;
        }
        else if (m_cmpFunc((AnyType *)pvData, pstRoot->pcData) < 0)
        {
            return SearchNode(pvData, pstRoot->pstLeftChild);
        }
        else if (m_cmpFunc((AnyType *)pvData, pstRoot->pcData) > 0)
        {
            return SearchNode(pvData, pstRoot->pstRightChild);
        }
        else
        {
            return NULL;
        }
    };

5. 删除最小节点

首先，用中序遍历的方法得到最小的节点，然后删除。

AnyType * DeleteSmallestNode()
    {
        GetSmallestNode(m_pstRoot);

        if (NULL == m_pstSmallestNode)
        {
            return NULL;
        }
        AnyType * pcData = m_pstSmallestNode->pcData;

        if (m_pstSmallestNode == m_pstRoot)
        {
            m_pstRoot = m_pstRoot->pstRightChild;
        }
        SetPointerThisNull(m_pstSmallestNode);

        free(m_pstSmallestNode);
        m_pstSmallestNode = NULL;

        return pcData;
    };

6. 析构函数

析构函数先用后续遍历节点，再对其进行删除。

7. 删除节点

删除节点的思路分为以下几种情况。

1）删除的是叶子节点，那么直接删除。

2）删除的节点左（右）子树为空，则用右（左）子树替代要删除的节点。

3）删除的节点左右子树都不为空，则用中序方法寻找此节点的前驱，用前驱替代此节点并删除。

bool DeleteTreeNode(void * pvData)
{
if (NULL == pvData)
{
return false;
}

TREE_NODE_T<AnyType> * pstTreeNode = SearchNode(pvData, GetRootNode());
if (!pstTreeNode)
{
return false;
}

if (pstTreeNode->pstLeftChild != NULL && pstTreeNode->pstRightChild != NULL)
{
TREE_NODE_T<AnyType> * pstForeNode = GetForeNodeMiddleOrder(pstTreeNode);
if (!pstForeNode)
{
return false;
}

memcpy(pstTreeNode->pcData, pstForeNode->pcData, sizeof(AnyType));

SetPointerThisNull(pstForeNode);
free(pstForeNode);
pstForeNode = NULL;

return true;
}


if (pstTreeNode->pstLeftChild == NULL && pstTreeNode->pstRightChild != NULL)
{
if (m_pstRoot == pstTreeNode)
{
m_pstRoot = pstTreeNode->pstRightChild;
pstTreeNode->pstRightChild->pstParent = NULL;
}
else
{
if (pstTreeNode == pstTreeNode->pstParent->pstLeftChild)
{
pstTreeNode->pstParent->pstLeftChild = pstTreeNode->pstRightChild;
}
if (pstTreeNode == pstTreeNode->pstParent->pstRightChild)
{
pstTreeNode->pstParent->pstRightChild = pstTreeNode->pstRightChild;
}
}
}
if (pstTreeNode->pstRightChild == NULL && pstTreeNode->pstLeftChild != NULL)
{
if (m_pstRoot == pstTreeNode)
{
m_pstRoot = pstTreeNode->pstLeftChild;
pstTreeNode->pstLeftChild->pstParent = NULL;
}
else
{
if (pstTreeNode == pstTreeNode->pstParent->pstLeftChild)
{
pstTreeNode->pstParent->pstLeftChild = pstTreeNode->pstLeftChild;
}
if (pstTreeNode == pstTreeNode->pstParent->pstRightChild)
{
pstTreeNode->pstParent->pstRightChild = pstTreeNode->pstLeftChild;
}
}

}

SetPointerThisNull(pstTreeNode);
free(pstTreeNode);
pstTreeNode = NULL;
return true;


};

总结：

除了SortBinaryTree提供的以上方法，大家还可以在此基础上进行适合自己项目的针对性扩展。由于做此排序二叉树是在写定时器时用来查找最先到时间的那个定时器，从而避免了对每个定时器进行扫描。因此，SortBinaryTree提供了一个删除最小节点的方法。

后续，将继续开源项目中抽象出的工具代码，请大家关注github上的源代码以及CSDN博客上的讲解。同时，也欢迎各路高手留下您宝贵的意见和建议。

秒客网

排序二叉树 SortBinaryTree

相关文章