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

　　/****************************************************************
　　*   函数名称：rotateWithLeftChild(AvlNode *t)
　　*   功能描述: 将当前结点进行单旋转，用于左左插入的时候
　　*   参数列表: t是指向当前结点的指针
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::rotateWithLeftChild(AvlNode * & k2)
　　{
　　cout << "左单旋转" << endl;
　　AvlNode * k1 = k2->left;
　　k2->left = k1->right;
　　k1->right = k2;
　　k2->height = max(height(k2->left)， height(k2->right)) + 1;
　　k1->height = max(height(k1->left)， k2->height) + 1;
　　k2 = k1;
　　}
　　/****************************************************************
　　*   函数名称：rotateWithRightChild(AvlNode *t)
　　*   功能描述: 将当前结点进行单旋转，用于左右插入的时候
　　*   参数列表: t是指向当前结点的指针
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::rotateWithRightChild(AvlNode * & k1)
　　{
　　cout << "右单旋转" << endl;
　　AvlNode * k2 = k1->right;
　　k1->right = k2->left;
　　k2->left = k1;
　　k1->height = max(height(k1->left)， height(k1->right)) + 1;
　　k2->height = max(height(k2->right)， k1->height) + 1;
　　k1 = k2;
　　}
　　/****************************************************************
　　*   函数名称：doubleWithLeftChild(AvlNode *t)
　　*   功能描述: 将当前结点进行双旋转，用于左右插入的时候
　　*   参数列表: t是指向当前结点的指针
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::doubleWithLeftChild(AvlNode * & k3)
　　{
　　cout << "**********************" << endl;
　　cout << "左双旋转: " << endl;
　　rotateWithRightChild(k3->left);
　　rotateWithLeftChild(k3);
　　cout << "**********************" << endl;
　　}
　　/****************************************************************
　　*   函数名称：doubleWithRightChild(AvlNode *t)
　　*   功能描述: 将当前结点进行双旋转，用于右左插入的时候
　　*   参数列表: t是指向当前结点的指针
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::doubleWithRightChild(AvlNode * & k1)
　　{
　　cout << "**********************" << endl;
　　cout << "右双旋转: " << endl;
　　rotateWithLeftChild(k1->right);
　　rotateWithRightChild(k1);
　　cout << "**********************" << endl;
　　}
　　/****************************************************************
　　*   函数名称：int height(AvlNode *t) const
　　*   功能描述: 获得当前结点t的高度
　　*   参数列表: t是指向当前结点的指针
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　int AvlTree<Comparable>::height(AvlNode * t) const
　　{
　　return (t == NULL) ? -1 : t->height;
　　}
　　/****************************************************************
　　*   函数名称：biggerOrderPrintTree()
　　*   功能描述: 按照从大到小的顺序输出该树结点
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::biggerOrderPrintTree()
　　{
　　cout << "从大到小输出：";
　　biggerOrderPrintTree(root);
　　cout << endl;
　　}
　　/****************************************************************
　　*   函数名称：biggerOrderPrintTree(AvlNode * t)
　　*   功能描述: 按照从大到小的顺序输出该树结点
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::biggerOrderPrintTree(AvlNode * t)
　　{
　　if(t != NULL){
　　biggerOrderPrintTree(t->right);
　　cout << t->element << " ";
　　biggerOrderPrintTree(t->left);
　　}
　　}
　　/****************************************************************
　　*   函数名称：lessOrderPrintTree()
　　*   功能描述: 按照从小到大的顺序输出该树结点
　　*   参数列表: 无
　　*   返回结果：无
　　*****************************************************************/
　　template<typename Comparable>
　　void AvlTree<Comparable>::lessOrderPrintTree()
　　{
　　cout << "从小到大输出：";
　　lessOrderPrintTree(root);   
　　cout << endl;
　　}