avltree.h

AVL平衡二叉树。原本在这里下载了其他人的平衡二叉树

/* 
AvlTree.h: AVL 平衡二叉树
*/

#if !defined(_AVL_SORTED_BALANCE_BINARY_TREE_H_)
#define _AVL_SORTED_BALANCE_BINARY_TREE_H_

typedef unsigned long   AVL_TREE_TYPE;


/* 创建一个AVL 平衡二叉树
*/
AVL_TREE_TYPE avlCreate();

/* 销毁一个AVL 平衡二叉树
*/
void avlDestroy(AVL_TREE_TYPE tree);

/* 插入一个结点
参数：w : 新结点的序号
      data : 新结点的数据
返回值：0 - 失败
        1 - 插入成功, 且树中原来没有该序号
		2 - 插入成功, 且树中原来有该序号
说明：如果树中原来有该序号的结点，则使用新的数据替换原来的数据
the bi-tree's weight is increased from left to right
*/
int avlInsert(AVL_TREE_TYPE tree, int w, unsigned long data);

/* 如果 avlInsert 插入的结点的序号与原来的某个结点序号相同，则返回原结点的数据；
否则返回0
*/
unsigned long avlGetDataBeforeInsert(AVL_TREE_TYPE tree);

/* 从树中删除一个结点
参数：w : 要删除的结点的序号
返回值：0 - 失败，没有找到该结点
        1 - 成功
*/
int avlRemove(AVL_TREE_TYPE tree, int w);

/* 查找某序号的结点
参数：w - 结点序号；
pData - 输出参数，用于获取结点的数据
返回值：0 - 没有找到；1 - 找到了
*/
int avlFind(AVL_TREE_TYPE tree, int w, unsigned long *pData);


/*-------------------------------------*/

typedef struct _AVL_NODE{
	struct _AVL_NODE *left;			/* left child */
	struct _AVL_NODE *right;		/* right child */
	struct _AVL_NODE *parent;		/* parent */
	int				height;			/* the height of the node */
	char			bf;				/* balance factor */
	int				weight;			/* 实际上就是虚拟块号(blkVirNum)，作为比较结点大小的值（权值） */
	unsigned long	data;			/* 结点中保存的数据：逻辑块号 */
} AVL_NODE, *PAVL_NODE;

PAVL_NODE avlGetRootNode(AVL_TREE_TYPE tree);


#endif /*  !defined(_AVL_SORTED_BALANCE_BINARY_TREE_H_) */