#include?“aatree.h“
#include?
#include?“fatal.h“

/*?START:?fig12_27.txt?*/
????????????/*?Returned?for?failures?*/
????????Position?NullNode?=?NULL;??/*?Needs?more?initialization?*/

????????struct?AANode
????????{
????????????ElementType?Element;
????????????AATree??????Left;
????????????AATree??????Right;
????????????int?????????Level;
????????};

????????AATree
????????Initialize（?void?）
????????{
????????????if（?NullNode?==?NULL?）
????????????{
????????????????NullNode?=?malloc（?sizeof（?struct?AANode?）?）;
????????????????if（?NullNode?==?NULL?）
????????????????????FatalError（?“Out?of?space!!!“?）;
????????????????NullNode->Left?=?NullNode->Right?=?NullNode;
????????????????NullNode->Level?=?0;
????????????}
????????????return?NullNode;
????????}
/*?END?*/

????????AATree
????????MakeEmpty（?AATree?T?）
????????{
????????????if（?T?!=?NullNode?）
????????????{
????????????????MakeEmpty（?T->Left?）;
????????????????MakeEmpty（?T->Right?）;
????????????????free（?T?）;
????????????}
????????????return?NullNode;
????????}

????????Position
????????Find（?ElementType?X?AATree?T?）
????????{
????????????if（?T?==?NullNode?）
????????????????return?NullNode;
????????????if（?X?Element?）
????????????????return?Find（?X?T->Left?）;
????????????else
????????????if（?X?>?T->Element?）
????????????????return?Find（?X?T->Right?）;
????????????else
????????????????return?T;
????????}

????????Position
????????FindMin（?AATree?T?）
????????{
????????????if（?T?==?NullNode?）
????????????????return?NullNode;
????????????else
????????????if（?T->Left?==?NullNode?）
????????????????return?T;
????????????else
????????????????return?FindMin（?T->Left?）;
????????}

????????Position
????????FindMax（?AATree?T?）
????????{
????????????if（?T?!=?NullNode?）
????????????????while（?T->Right?!=?NullNode?）
????????????????????T?=?T->Right;

????????????return?T;
????????}

????????/*?This?function?can?be?called?only?if?K2?has?a?left?child?*/
????????/*?Perform?a?rotate?between?a?node?（K2）?and?its?left?child?*/
????????/*?Update?heights?then?return?new?root?*/

????????static?Position
????????SingleRotateWithLeft（?Position?K2?）
????????{
????????????Position?K1;

????????????K1?=?K2->Left;
????????????K2->Left?=?K1->Right;
????????????K1->Right?=?K2;

????????????return?K1;??/*?New?root?*/
????????}

????????/*?This?function?can?be?called?only?if?K1?has?a?right?child?*/
????????/*?Perform?a?rotate?between?a?node?（K1）?and?its?right?child?*/
????????/*?Update?heights?then?return?new?root?*/

????????static?Position
????????SingleRotateWithRight（?Position?K1?）
????????{
????????????Position?K2;

????????????K2?=?K1->Right;
????????????K1->Right?=?K2->Left;
????????????K2->Left?=?K1;

????????????return?K2;??/*?New?root?*/
????????}

/*?START:?fig12_29.txt?*/
????????/*?If?T‘s?left?child?is?on?the?same?level?as?T?*/
????????/*?perform?a?rotation?*/

????????AATree
????????Skew（?AATree?T?）
????????{
????????????if（?T->Left->Level?==?T->Level?）
????????????????T?=?SingleRotateWithLeft（?T

?屬性????????????大小?????日期????時(shí)間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-06-29?11:09??answer\
?????文件????????4112??2001-09-19?12:54??answer\ch00.pdf
?????文件???????11708??2001-09-19?12:54??answer\ch01.pdf
?????文件???????14778??2001-09-19?12:54??answer\ch02.pdf
?????文件???????15330??2001-09-19?12:55??answer\ch03.pdf
?????文件???????29060??2001-09-19?12:55??answer\ch04.pdf
?????文件???????13390??2001-09-19?12:55??answer\ch05.pdf
?????文件???????32039??2001-09-19?12:55??answer\ch06.pdf
?????文件???????22231??2001-09-19?12:55??answer\ch07.pdf
?????文件???????14724??2001-09-19?12:55??answer\ch08.pdf
?????文件???????42865??2001-09-19?12:55??answer\ch09.pdf
?????文件???????45488??2001-09-19?12:56??answer\ch10.pdf
?????文件???????13333??2001-09-19?12:56??answer\ch11.pdf
?????文件????????4435??2001-09-19?12:56??answer\ch12.pdf
?????目錄???????????0??2015-06-29?11:09??code\
?????文件????????6181??1996-08-13?03:27??code\aatree.c
?????文件?????????669??1997-11-05?09:33??code\aatree.h
?????文件????????5593??1996-08-13?03:27??code\avltree.c
?????文件?????????583??1997-11-05?09:34??code\avltree.h
?????文件????????3364??1996-08-13?03:27??code\binheap.c
?????文件?????????588??1997-11-05?09:34??code\binheap.h
?????文件????????6727??1996-08-13?03:27??code\binomial.c
?????文件?????????762??1997-11-05?09:34??code\binomial.h
?????文件????????4474??1996-08-13?03:27??code\cursor.c
?????文件?????????890??1997-11-05?09:35??code\cursor.h
?????文件????????2564??1996-08-13?03:27??code\disjsets.c
?????文件????????4737??1996-08-13?03:27??code\dsl.c
?????文件?????????701??1997-11-05?09:35??code\dsl.h
?????文件?????????156??2008-08-11?20:03??code\fatal.h
?????文件?????????848??1996-08-13?03:27??code\fig10_38.c
?????文件?????????808??1996-08-13?03:27??code\fig10_40.c
............此處省略60個(gè)文件信息