数据结构与算法AVL树类的C++实现

　　/****************************************************************
　　*   函数名称：findMax()
　　*   功能描述: 找到该树的大值
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　Comparable AvlTree<Comparable>::findMax() const
　　{
　　if(!isEmpty())
　　return findMax(root);
　　}
　　/****************************************************************
　　*   函数名称：findMax(AvlNode * t)
　　*   功能描述: 找到该树的大值
　　*   参数列表: t表示当前结点
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　Comparable AvlTree<Comparable>::findMax(AvlNode * t) const
　　{
　　if(t->right== NULL)
　　return t->element;
　　else
　　return findMax(t->right);
　　}
　　/****************************************************************
　　*   函数名称：findMin()
　　*   功能描述: 找到该树的小值
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　Comparable AvlTree<Comparable>::findMin() const
　　{
　　if(!isEmpty())
　　return findMin(root);
　　}
　　/****************************************************************
　　*   函数名称：findMin(AvlNode * t)
　　*   功能描述: 找到该树的小值
　　*   参数列表: t表示当前结点
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　Comparable AvlTree<Comparable>::findMin(AvlNode * t) const
　　{
　　if(t->left == NULL)
　　return t->element;
　　else
　　return findMin(t->left);
　　}
　　/****************************************************************
　　*   函数名称：~AvlTree()
　　*   功能描述: 析构函数，释放结点内存空间
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　AvlTree<Comparable>::~AvlTree()
　　{
　　makeEmpty();
　　}
　　/****************************************************************
　　*   函数名称：void insert(const Comparable & x)
　　*   功能描述: 插入值为x的结点
　　*   参数列表: x为要插入结点的值
　　*   返回结果：void
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::insert(const Comparable & x)
　　{
　　insert(x， root);
　　}
　　/****************************************************************
　　*   函数名称：void insert(const Comparable & x， AvlNode * t)
　　*   功能描述: 在结点t的后面插入值为x的结点
　　*   参数列表: x为要插入结点的值
　　*             t为当前的结点
　　*   返回结果：void
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::insert(const Comparable & x， AvlNode * & t)
　　{
　　if(t == NULL)//当前结点为空
　　t = new AvlNode(x， NULL， NULL);
　　else if(x < t->element){
　　insert(x， t->left);
　　if(height(t->left) - height(t->right) == 2){
　　if(x < t->left->element)//单旋转，左左插入
　　rotateWithLeftChild(t);
　　else
　　doubleWithLeftChild(t);//双旋转，左右插入
　　}
　　}
　　else if(x > t->element){
　　insert(x， t->right);
　　if(height(t->right) - height(t->left) == 2){
　　if(x > t->right->element)//单旋转，右右插入
　　rotateWithRightChild(t);
　　else
　　doubleWithRightChild(t);//双旋转，右左插入
　　}
　　}
　　//如果x的值和当前结点的值相同，则忽略。也可以向之前二叉查找树一样给每个结点再加一个num成员变量。
　　t->height = max(height(t->left)， height(t->right)) + 1;//更新结点t的高度
　　}