template typename AVLTree::Node* & AVLTree::getParent(Node* p)
{?
? ? if( p == m_root)?
? ? ? ? return NULL;?
? ? Node* ptr = m_root;?
? ? Node* ptf = ptr;?
? ? while( ptr != NULL )?
? ? {?
? ? ? ? if ( ptr->e == p->e )?
? ? ? ? ? ? return ptf;?
? ? ? ? if ( ptr->e > p->e )?
? ? ? ? {?
? ? ? ? ? ? ptf = ptr;?
? ? ? ? ? ? ptr = ptr->leftChild;?
? ? ? ? }?
? ? ? ? else?
? ? ? ? {?
? ? ? ? ? ? ptf = ptr;?
? ? ? ? ? ? ptr = ptr->rightChild;
? ? ? ? }?
? ? }?
}

template typename AVLTree::Node*& AVLTree::find(Type e)const
{?
? ? Node* ptr = m_root;?
?
? ? while(ptr != NULL)?
? ? {?
? ? ? ? if ( ptr->e == e )?
? ? ? ? ? ? return ptr;?
? ? ? ? if ( ptr->e > e )?
? ? ? ? ? ? ptr = ptr->leftChild;?
? ? ? ? else?
? ? ? ? ? ? ptr = ptr->rightChild;?
? ? }?
? ? //if ( ptr == NULL )?
? ? return NULL;?
}

template void AVLTree::clears(Node*& p)
{
?if( p == NULL )
? return;
?else
?{
? clears(p->left);
? clears(p->right);
? delete p;
? p = NULL;
? mLength--;
?}
}

template void AVLTree::clear()
{
?clears(mRoot);
}

template void AVLTree::erase(Type e,Node* &p)
{
?if( p == NULL)
? return;
?if( e > p->e)
?{
? erase(e,p->right);
? if( height(p->left) - height(p->right) == 2)
? {
? ?if( height(p->left->left) > height(p->left->right) )
? ? rotateLeft(p);
? ?else
? ? rotateLeftDouble(p);
? }
?}
?else if( e < p->e)
?{
? erase(e,p->left);
? if( height(p->left) - height(p->right) == -2)
? {
? ?if( height(p->right->right) > height(p->right->left) )
? ? rotateRight(p);
? ?else
? ? rotateRightDouble(p);
? }
?}
?else if ( e == p->e && p->left!= NULL && p->right!= NULL)
?{
? Node* pmax = p->left;
? while( pmax->right != NULL)
? {
? ?pmax = pmax->right;
? }
? p->e = pmax->e;
? erase(p->e,p->left);
?}
?else //最终的删除会在这里执行
?{
? Node* pNew = p->left==NULL ? p->right : p->left;
? delete p;
? p = pNew;
? mLength--;
?}
?if ( p!=NULL)
? p->h = max( height(p->left),height(p->right)) + 1;
}
#endif

//main.cpp

#include
#include "AVLTree.h"
using namespace std;

void main()
{
?int Arr[9] = {6,2,8,4,10,0,12,16,14};
?AVLTree Tr(Arr,9);
?Tr.traverse(Tr.getRoot());
?Tr.traverseByLevel(Tr.getRoot());

?Tr.erase(14,Tr.getRoot());
?Tr.traverse(Tr.getRoot());
?Tr.traverseByLevel(Tr.getRoot());
?cout<<"Tree's length is:"<?Tr.clear();
?cout<<"Tree's length is:"<

}

4 测试结果

将C语言梳理一下，分布在以下10个章节中：