c语言树实现文件,AA树实现文件C语言

/*AATree.c -- AA树实现文件*/

#include "AATree.h"

/*全局变量声明*/

static Node * NullNode &＃61; NULL ;

/*局部函数声明*/

static Node * singleRotateWithLeft (Node * const pn) ;

static Node * singleRotateWithRight (Node * const pn) ;

static Node * skew (Node * pn) ;

static Node * split (Node * pn) ;

static void release (AATree aat) ;

/*接口函数定义*/

Node * Initialize_A (void)

{

if (NULL &＃61;&＃61; NullNode)

{

NullNode &＃61; (Node *) malloc (sizeof (Node)) ;

if (NULL &＃61;&＃61; NullNode)

return NULL ;

NullNode -> left &＃61; NullNode -> right &＃61; NullNode ;

NullNode -> level &＃61; 0 ;

}

return NullNode ;

}

AATree Insert_A (AATree aat, const Item item)

{

if (aat &＃61;&＃61; NullNode)

{

/*Create and return a one-node tree.*/

aat &＃61; (Node *) malloc (sizeof (Node)) ;

if (NULL &＃61;&＃61; aat)

puts ("Out of space.") ;

else

{

aat -> item &＃61; item ;

aat -> level &＃61; 1 ;

aat -> left &＃61; aat -> right &＃61; NullNode ;

}

return aat ;

}

else if (item item)

aat -> left &＃61; Insert_A (aat -> left, item) ;

else if (item > aat -> item)

aat -> right &＃61; Insert_A (aat -> right, item) ;

/*Otherwise it&＃39;s a duplicate; do nothint.*/

aat &＃61; skew (aat) ;

aat &＃61; split (aat) ;

return aat ;

}

BOOL Find_A (AATree aat, const Item item)

{

Node * scan &＃61; aat ;

while (scan !&＃61; NullNode)

{

if (item item)

scan &＃61; scan -> left ;

else if (item > scan -> item)

scan &＃61; scan -> right ;

else

return TRUE ;

}

return FALSE ;

}

int Count_A (AATree aat)

{

static count &＃61; 0 ;

if (aat !&＃61; NullNode)

{

Count_A (aat -> left) ;

Count_A (aat -> right) ;

count&＃43;&＃43; ;

return count ;

}

else

return 0 ;

}

AATree Delete_A (AATree aat, const Item item)

{

static Node * deletePtr, * lastPtr ;

if (aat !&＃61; NullNode)

{

/*Step 1:Search down tree.*/

/*Set lastPtr and deletePtr.*/

lastPtr &＃61; aat ;

if (item item)

aat -> left &＃61; Delete_A (aat -> left, item) ;

else

{

deletePtr &＃61; aat ;

aat -> right &＃61; Delete_A (aat -> right, item) ;

}

/*Step 2:If at the bottom of the tree and*/

/*item is present, we delete it.*/

if (aat &＃61;&＃61; lastPtr)

{

if (deletePtr !&＃61; NullNode && item &＃61;&＃61; deletePtr -> item)

{

deletePtr -> item &＃61; aat -> item ;

deletePtr &＃61; NullNode ;

aat &＃61; aat -> right ;

free (lastPtr) ;

}

}

/*Step 3:Otherwise, we are not at the bottom.*/

/*Rebalance.*/

else

{

if (aat -> left -> level level - 1 ||

aat -> right -> level level - 1)

{

if (aat -> right -> level > --aat -> level)

aat -> right -> level &＃61; aat -> level ;

aat &＃61; skew (aat) ;

aat -> right &＃61; skew (aat -> right) ;

aat -> right -> right &＃61; skew (aat -> right -> right) ;

aat &＃61; split (aat) ;

aat -> right &＃61; split (aat -> right) ;

}

}

}

return aat ;

}

void Release_A (AATree aat)

{

Release_A (aat) ;

free (NullNode) ;

NullNode &＃61; NULL ;

}

/*局部函数定义*/

static Node * singleRotateWithLeft (Node * const pn)

{

Node * left ;

left &＃61; pn -> left ;

pn -> left &＃61; left -> right ;

left -> right &＃61; pn ;

return left ;

}

static Node * singleRotateWithRight (Node * const pn)

{

Node * right ;

right &＃61; pn -> right ;

pn -> right &＃61; right -> left ;

right -> left &＃61; pn ;

return right ;

}

static Node * skew (Node * pn)

{

if (pn -> left -> level &＃61;&＃61; pn -> level)

pn &＃61; singleRotateWithLeft (pn) ;

return pn ;

}

static Node * split (Node * pn)

{

if (pn -> right -> right -> level &＃61;&＃61; pn -> level)

{

pn &＃61; singleRotateWithRight (pn) ;

pn -> level&＃43;&＃43; ;

}

return pn ;

}

static void release (AATree aat)

{

if (aat !&＃61; NullNode)

{

release (aat -> left) ;

release (aat -> right) ;

free (aat) ;

}

}