avl.cpp

来自「数据结构c++语言描述 Borland C++实现」· C++ 代码 · 共 134 行

#include <iostream.h>
#include "avl.h"


void main(void)
{
   AVLtree<int,int> y;

   // first test insert and ascending output
   y.Insert(21).Insert(26).Insert(30);
   cout << "An RR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(9).Insert(4);
   cout << "An LL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(14);
   cout << "An LR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(28);
   cout << "An RL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(18).Insert(15);
   cout << "An RL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(10);
   cout << "An RL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(2);
   cout << "An LL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(3);
   cout << "An LR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(7);
   cout << "An LR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();

   // now test the delete operation
   int x;
   y.Delete(2,x).Delete(3,x);
   cout << "An L0/RR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Delete(10,x);
   cout << "An R-1/LR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Delete(18,x).Delete(4,x).Delete(9,x);
   cout << "An L-1/RR rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Delete(30,x).Delete(14,x).Delete(7,x).Delete(15,x);
   cout << "An L1/RL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(10).Insert(5).Insert(30).Insert(29);
   y.Delete(29,x).Delete(28,x).Delete(30,x);
   cout << "An R0/LL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
   y.Insert(3);
   y.Delete(26,x).Delete(21,x);
   cout << "An R1/LL rotation has been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();
 
   // empty out and create larger tree
   y.Delete(5,x).Delete(3,x).Delete(10,x);

   y.Insert(40).Insert(5).Insert(50).Insert(3);
   y.Insert(10).Insert(45).Insert(60);
   y.Insert(1).Insert(7).Insert(30).Insert(41);
   y.Insert(47).Insert(55).Insert(70).Insert(20);
   y.Insert(46).Insert(52).Insert(65).Insert(72).Insert(68);

   // should cause multiple rotations
   y.Delete(3,x);
   cout << "Two L-1/RR rotations have been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();

   y.Insert(58).Insert(56).Insert(74).Insert(71).Insert(75);
   // should cause multiple rotations
   y.Delete(5,x).Delete(1,x).Delete(7,x);
   y.Delete(20,x).Delete(10,x).Delete(30,x);
   cout << "An L1/RL followed by two L-1/RR rotations have been done" << endl;
   cout << "Elements in ascending order are" << endl;
   y.Ascend();
   cout << "Elements in postorder order are" << endl;
   y.PostOut();

}