AVL树模板,支持操作如下
template <class T>
struct BSTNode {
T data;
int h;
BSTNode<T> * lchild, *rchild;
};
template <class T>
class AVLTree {
public:
AVLTree() :root(NULL),node_num(0) {}
~AVLTree() { Release(root); }
void Clear() { Release(root); root = NULL; }
bool Insert(T x) { return Insert(root, x); }
bool Delete(T x) { return Delete(root, x); }
BSTNode<T> * Search(T x) { return Search(root, x); }
vector<T> PreOrder() { vector<T>vec; PreOrder(root, vec); return vec; }
vector<T> InOrder() { vector<T>vec; InOrder(root, vec); return vec;}
vector<T> PostOrder() { vector<T>vec; PostOrder(root, vec); return vec;}
vector<T> LevelOrder() { vector<T>vec; LevelOrder(root, vec); return vec;}
inline size_t size() { return node_num; }
private:
size_t node_num;
BSTNode<T> * root;
void Release(BSTNode<T> * bst);
inline int Height(BSTNode<T> * bst) { return (bst == NULL ? -1 : bst->h); }
void SingleRotateWithLeft(BSTNode<T> * &bst;); //LL型
void DoubleRotateWithLeft(BSTNode<T> * &bst;); //LR型
void SingleRotateWithRight(BSTNode<T> * &bst;); //RR型
void DoubleRotateWithRight(BSTNode<T> * &bst;); //RL型
bool Insert(BSTNode<T> * &bst;, const T &x);
bool Delete(BSTNode<T> * &bst;, const T &x);
BSTNode<T> * Search(BSTNode<T> * bst, T &x);
void PreOrder(BSTNode<T> * bst, vector<T>&vec;);
void InOrder(BSTNode<T> * bst, vector<T>&vec;);
void PostOrder(BSTNode<T> * bst, vector<T>&vec;);
void LevelOrder(BSTNode<T> * bst, vector<T>&vec;);
};