Avl平衡二叉树 win32 SDK — 编程爱好者社区

1          概述
本文档适用于C语言开发人员，文档详细讲述Avl平衡二叉树SDK中每个函数的

用法以及源码示例。

2          Avl平衡二叉树介绍
参考相关文档。

3          Avl二叉树SDK技术特点
支持以下功能：

1、支持自定义键值比较函数

2、支持删除节点回调函数

3、支持插入节点

4、支持根据键值进行精确查询节点

5、支持根据键值进行精确删除节点

6、支持从头到尾（从尾到头）遍历树

非递归方式

7、支持从任意指定节点开始向下（或向上）遍历节点

8、支持范围查询（>、>=、<=、< ）

9、支持删除头（尾）节点

10、支持获取头（尾）节点

11、支持获取节点数量

12、支持清空所有节点数量

13、支持节点缓冲

4          Avl二叉树应用场景
1、海量数据查询

2、数据排序

3、其它情况

5          定义说明
1、HAVLTREE

   指向一个Avl树的句柄，即指向alv树的指针，定义如下：

   typedef void* HAVLTREE;

2、POSITION

   POSITION定义为一个指向Avl节点的指针，定义如下：

    typedef void* POSITION;

3、HANDLE

定义如下：

    typedef void* HANDLE;

    在本文里指Avl节点中用户数据

4、ONAVLCOMPARE

    typedef int (* ONAVLCOMPARE)(void* pNodeKey, void* pOutKey);

    参数说明：

1、void* pNodeKey

输入参数，为Avl树节点的键值指针

  2、void* pOutKey

   输入参数，为外部提供的键值

返回值：

> 0：说明此Avl树节点大于外部键值

= 0：说明此Avl树节点等于外部键值

< 0：说明此Avl树节点小于外部键值

5、avl节点内部定义如下：

    typedef struct _BSTNODE

{

        _BSTNODE* pParent; // 父节点

        _BSTNODE* pLeftChild;  // 左节点

        _BSTNODE* pRightChild;  // 右节点

        char nHeight;      // 高度

        void* pKey;       // 节点键值

        HANDLE hValue;    // 用户数据

}BSTNODE;

typedef BSTNODE* LPBSTNODE;

6、ONAVLDELETE

ONAVLDELETE为回调函数指针，在执行AvlDeleteTree和AvlRemoveAll

函数释放树节点时，对每个被删除的节点都执行此回调函数，在回调函数中

处理与节点相关的操作。

定义如下：

typedef bool (* ONAVLDELETE)(POSITION pos, void* pInputPara);

参数：

1）POSITION pos

       被删除Avl节点句柄（指针）

    2）void* pInputPara

输入参数指针，由AvlDeleteTree和AvlRemoveAll函数的参数中提供。

7、头节点

Avl树中键值最小的节点

8、尾节点

Avl树中键值最大的节点

9、下一节点

Avl树中键值比当前节点大的第一个节点

10、上一节点

Avl树中键值比当前节点小的第一个节点

6          avl平衡二叉树SDK功能函数
6.1     AvlCreateTree ()

1、功能说明

此函数用来生成一个FIFO消息队列，执行成功后返回消息队列句柄，之后对

此Avl树的操作都引用此句柄。

2、函数原型

HAVLTREE AvlCreateTree(ONAVLCOMPARE OnCompare);

3、参数说明

1）ONAVLCOMPARE OnCompare

比较Avl树中节点和外部输入键值的函数指针，请参考上一章关于此函数指针的定义

4、返回值

返回Avl树的句柄

5、相关函数

   AvlDeleteTree()

示例1：

功能：生成一个Avl树,比较函数是对int数据类型进行比较。

#include "AvlAPI.h"

int OnCompare(void* pNodeKey, void* pOutKey)

{

    if (int(pNodeKey) > int(pOutKey))

    {

        return 1;

    }

    else if (int(pNodeKey) < int(pOutKey))

    {

        return -1;

    }

    else

    {

        return 0;

    }

}

int main(int argc, char* argv[])

{

HAVLTREE hTree;

hTree = AvlCreateTree(OnCompare);

    return 0;

}

示例2：

功能：生成一个Avl树,比较函数是对字符串进行比较。

#include "AvlAPI.h"

int OnCompare(void* pNodeKey, void* pOutKey)

{

    return(strcmp((char *)pNodeKey, (char *)pOutKey));

}

int main(int argc, char* argv[])

{

HAVLTREE hTree;

hTree = AvlCreateTree(OnCompare);

    return 0;

}

6.2  AvlDeleteTree()
1、功能说明

此函数用来删除Avl树以及树中的节点，删除后的Avl树句柄不能再被引用。

2、函数原型

void AvlDeleteTree(HAVLTREE hTree, ONAVLDELETE OnDelete = NULL,

void* pInputPara = NULL);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

   2）ONAVLDELETE OnDelete = NULL

参考上一章关于此函数指针的说明，如果此参数设置为NULL，则在删除Avl

树时不调用此回调函数。

3）void* pInputPara;

由开发人员设置自己的数据，一般为结构体或对象的指针，由回调函数

使用。

4、返回值

    无

6.3     AvlAddKey()
1、功能说明

此函数用来在Avl树中增加节点。

2、函数原型

bool AvlAddKey(HAVLTREE hTree, void* pKey, HANDLE hValue,

POSITION& pos);

3、参数说明

   1）HAVLTREE hTree

      消息队列句柄，此句柄由MQCreateQueue函数生成。

2）void* pKey

pKey为键值，pKey可以本身是键值，也可以是指向某地址的指针，在

AvlAddKey函数执行时直接把pKey值赋给Avl节点中的pKey成员变量。

3）HANDLE hValue

用户数据句柄（指针）在，AvlAddKey函数执行时直接把hValue赋给Avl

节点中的hValue成员变量。

4）POSITION& pos;

输出参数，返回新增节点的句柄，如果新增节点失败，pos值为NULL。

4、返回值

    1）true

添加节点成功。

   2）false

       添加节点失败，树中存在相同主键的节点

6.4     AvlRemoveKey()
1、功能说明

此函数用来在Avl树中根据键值删除指定的节点。

2、函数原型

bool AvlRemoveKey(HAVLTREE hTree, void* pKey, HANDLE& hValue);

3、参数说明

   1）HAVLTREE hTree

      输入参数

      Avl树句柄，此句柄由AvlCreateTree函数生成。

2）void* pKey

输入参数，删除节点的键值

3）HANDLE& hValue

输出参数

返回要删除节点的用户数据句柄（指针）

4、返回值

    1）true

从Avl树中成功删除一个节点。

   2）false

      在Avl中不存在指定键值的节点

6.5     AvlGetCount()
1、功能说明

此函数用来获取Avl树中节点的数量。

2、函数原型

int AvlGetCount(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回消息的数量



6.6     AvlRemoveAll()
1、功能说明

此函数用来清除Avl树中所有的节点。

2、函数原型

void AvlRemoveAll(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回消息的数量

6.7     AvlGetKeyPosition()
1、功能说明

此函数用来根据键值在Avl树中查询节点，返回节点的句柄。

2、函数原型

POSITION AvlGetKeyPosition(HAVLTREE hTree, void* pKey);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

2) 查询节点用的键值

4、返回值

    返回节点的句柄，如果返回值为NULL，则没有查询到节点。



6.8     AvlGetKeyValue()
1、功能说明

此函数用来根据键值在Avl树中查询节点，返回节点的用户数据。

2、函数原型

bool AvlGetKeyValue(HAVLTREE hTree, void* pKey, HANLDE& hValue);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

2) void* pKey

  查询节点用的键值

3) HANDLE& hValue

  输出参数，返回节点用户数据

4、返回值

    true：查询到该键值的节点

    false：没有此键值的节点


6.9     AvlGetHeadPosition()
1、功能说明

此函数用来返回Avl树中的头节点即键值最小的节点。

2、函数原型

POSITION AvlGetHeadPosition(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄，如果Avl树中没有节点返回值为NULL，否则返回非空值。

6.10        AvlGetNextPosition()
1、功能说明

此函数用来返回Avl树中指定节点的下一个节点,下一个节点的键值大于当前节点的键值,如果当前节点是最后一个节点，则返回NULL。

2、函数原型

POSITION AvlGetNextPosition(POSITION pos);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

    2）POSITION pos

       指定节点

4、返回值

    返回节点句柄，如果Avl树中没有节点返回值为NULL，否则返回非空值。



示例：参考AvlGetHeadPosition

6.11        AvlGetPrevPosition()
1、功能说明

此函数用来返回Avl树中指定节点的上一个节点,上一个节点的键值小于当前节点的键值,如果当前节点是头节点，则返回NULL。

2、函数原型

POSITION AvlGetPrevPosition(POSITION pos);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

    2）POSITION pos

       指定节点

4、返回值

    返回节点句柄，如果Avl树中没有节点返回值为NULL，否则返回非空值。

示例：参考AvlGetHeadPosition

6.12        AvlGetTailPosition()
1、功能说明

此函数用来返回Avl树中的尾节点即键值最大的节点。

2、函数原型

POSITION AvlGetTailPosition(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄，如果Avl树中没有节点返回值为NULL，否则返回非空值。



6.13        AvlRemoveHead()
1、功能说明

此函数删除Avl树中的头节点即键值最小的节点，同时返回被删除节点的句柄值。注意使用此函数时，必须确保树中必须非空，否则运行出异常错误。

2、函数原型

HANDLE AvlRemoveHead(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回被删除头节点的句柄值。

6.14        AvlRemoveTail()
1、功能说明

此函数删除Avl树中的尾节点即键值最大的节点，同时返回被删除节点的句柄值。注意使用此函数时，必须确保树中必须非空，否则运行出异常错误。

2、函数原型

HANDLE AvlRemoveTail(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回被删除尾节点的句柄值。

6.15        AvlGetFirstPosGEKey()
1、功能说明

此函数返回Avl树中的第一个键值大于等于指定键值的节点,如果没有满足条件的节点返回NULL。

2、函数原型

POSITION AvlGetFirstPosGEKey(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄。



6.16        AvlGetFirstPosGTKey()
1、功能说明

此函数返回Avl树中的第一个键值大于指定键值的节点,如果没有满足条件的节点返回NULL。

2、函数原型

POSITION AvlGetFirstPosGTKey(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄。

6.17        AvlGetFirstPosSEKey()
1、功能说明

此函数返回Avl树中的第一个键值小于等于指定键值的节点,如果没有满足条件的节点返回NULL。

2、函数原型

POSITION AvlGetFirstPosSEKey(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄。



6.18        AvlGetFirstPosSTKey()
1、功能说明

此函数返回Avl树中的第一个键值小于指定键值的节点,如果没有满足条件的节点返回NULL。

2、函数原型

POSITION AvlGetFirstPosSEKey(HAVLTREE hTree);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回节点句柄。


6.19        AvlGetPosKey()
1、功能说明

此函数用来获取指定节点的键值。

2、函数原型

void* AvlGetPosKey(POSITION pos);

3、参数说明

   1）POSITION pos

      节点句柄

4、返回值

    返回节点键值。



5、相关函数

AvlGetPosValue()

示例：

参考函数AvlGetHeadPosition示例中的关于AvlGetPosKey用法。

6.20        AvlGetPosValue()
1、功能说明

此函数用来获取指定节点的用户数据句。

2、函数原型

HANDLE AvlGetPosValue(POSITION pos);

3、参数说明

   1）POSITION pos

      节点句柄。

4、返回值

    返回节点的句柄值。



5、相关函数

AvlGetPosKey()

示例：

参考函数AvlGetHeadPosition示例中的关于AvlGetPosValue用法。

6.21        AvlSetPosValue()
1、功能说明

此函数用来设置指定节点的用户数据。

2、函数原型

void AvlSetPosValue(POSITION pos, HANDLE hValue);

3、参数说明

   1）HAVLTREE hTree

      Avl树句柄。

4、返回值

    返回被删除尾节点的句柄值。

主题：Avl平衡二叉树 win32 SDK

回复列表（共0个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

主题：Avl平衡二叉树 win32 SDK

回复列表 （共0个回复）

我来回复

程序员工具箱 new

代码片段

本版新帖

回复列表（共0个回复）