学步园

我的第一颗AVL树.弄了一天,虽然还没有最终测试完毕./* AVLTree.h -- AVl树头文件 */</p> <p>/* 数据类型定义 */</p> <p>typedef int Item ;<br /> typedef struct node<br /> {<br /> Item item ;<br /> struct node * left ;<br /> struct node * right ;<br /> int height ;<br /> } Node ;<br /> typedef Node * Position ;<br /> typedef Position Tree ;</p> <p>/* 接口函数声明 */</p> <p>/* 操作: 初始化一棵AVL树 */<br /> /* 操作前: ptree 指向一棵AVL树 */<br /> /* 操作后: 该树被初始化为空树 */<br /> void InitializeAVLTree (Tree * ptree) ;</p> <p>/* 操作: 确定AVL树是否为空 */<br /> /* 操作前: tree 是一棵已初始化的AVL树 */<br /> /* 操作后: 如果该树为空, 返回1; 否则返回0 */<br /> int AVLTreeIsEmpty (const Tree tree) ;</p> <p>/* 操作: 返回树中指定数据所在结点 */<br /> /* 操作前: tree 是一棵已初始化的AVL树, item 是被查找的数据 */<br /> /* 操作后: 如果可能, 返回被查找数据所在结点的地址; 否则返回? */<br /> Position Find (const Tree tree, const Item item) ;</p> <p>/* 操作: 返回树中最大数据所在结点位置 */<br /> /* 操作前: tree 是一棵已初始化的AVL树 */<br /> /* 操作后: 如果可能, 返回树中最大数据所在结点的位置; 否则返回NULL */<br /> Position FindMax (const Tree tree) ;</p> <p>/* 操作: 返回树中最小数据所在结点位置 */<br /> /* 操作前: tree 是一棵已初始化的AVL树 */<br /> /* 操作后: 如果可能, 返回树中最小数绝所在结点的位置; 否则返回NULL */<br /> Position FindMin (const Tree tree) ;</p> <p>/* 操作: 向AVL树中插入结点 */<br /> /* 操作前: tree 是一棵已初始化的AVL树, item 是准备插入结点的指定数据 */<br /> /* 操作后: 如果可能, 返回插入结点后的新树; 否则返回原树 */<br /> Tree Insert (Tree tree, const Item item) ;</p> <p>/* 操作: 以中序遍历将一个函数作用于AVL树中的所有结点 */<br /> /* 操作前: tree 是一棵已初始化的AVL树, pfun 指向一个没有返回值, 接受一个 Position 类型参数的函数 */<br /> /* 操作后: 该函数被作用到该树的所有结点, 后序中历方式 */<br /> void PostorderTraverse (const Tree tree, void (* pfun) (const Position position)) ;</p> <p>/* 操作: 删除AVL树中指定数据所在结点 */<br /> /* 操作前: tree 是一棵已初始化的AVL树, item 是被删除的数据 */<br /> /* 操作后: 如果可能, 删除该数据所在结点, 并调整树符合AVL树特性, 返回树根结点地址; 否则不做更改, 返回树根结点地址 */<br /> Tree Delete (Tree tree, const Item item) ;</p> <p>/* 操作: 清空一棵AVL树 */<br /> /* 操作前: tree 是一棵已初始化的AVL树 */<br /> /* 操作后: 该树被清空 */<br /> void EmptyTheAVLTree (Tree tree) ;