//this is avl tree class
#include "AVLNode.h"

template <class T> class avlTree//平衡二叉樹類
{
	public:
		avlTree();//構造函數
		avlTree(const avlTree<T> &source);
		~avlTree();//析構函數
		void add(T value);
		void remove(T value);
		void deleteAllValue();
		void display();
		void display(avlNode<T>* found);
		avlNode<T>* findValue(T val);
	private:
		avlNode<T> *root;
};


template <class T>avlTree<T>::avlTree<T>():root(0)
{}//建立空樹
template <class T>avlTree<T>::avlTree<T>(const avlTree<T> &source)
{//復制構造函數
	root=(source.root==NULL?NULL:source.root->copy());
}
template <class T> avlTree<T>::~avlTree()
{
	if (root!=NULL) deleteAllValue();
}
template <class T> void avlTree<T>::add(T value)
{//向平衡的avl樹添加元素
	if(root==NULL)
		root=new avlNode<T>(value);
	else
		root->add(root,value);
}

template <class T> void avlTree<T>::remove(T val)
{//從avl樹中刪除一個元素
	avlNode<T>* eNode=NULL;
	int flag=0;
	if (root)
		root=root->remove(val,eNode,flag);
	if (eNode)
		delete eNode;
	else cout<<"The avlTree doesn't contain the value"<<endl;
}

template <class T> void avlTree<T>::deleteAllValue()
{//刪除avl樹的全部元素
	if(root!=NULL)
	{
		root->release();
		delete root;
		root=NULL;
	}
}
template <class T> void avlTree<T>::display()
{
	if (root) 
	{
		cout<<setw(8)<<"節點值"<<setw(10)<<"平衡因子"<<" "<<setw(6)<<"層數"<<endl;
		root->preorderview(root);
	}
	else cout<<"當前樹空!"<<endl;
}
template <class T> avlNode<T>* avlTree<T>::findValue(T val)
{//查找val的節點值
	avlNode<T>* found=root->findNodeValue(val);
	if (found==NULL)
		return NULL;
	else
		return found;
}
template <class T> void avlTree<T>::display(avlNode<T>* found)
{//顯示指針的指向的碼值
	if(found==NULL) 
		cout<<"Sorry,沒找到 :("<<endl;
	else
		cout<<"找到:"<<found->value<<endl;
}