数据结构与算法分析：二叉树

二叉树数据结构与算法1二叉查找树BinarySearchTreesBST特性:对于二叉查找树的任何一个结点，设其值为K

,则该结点在左子树中的任意一个结点的值都小于K.该结点右子树中任意一个结点的值都大于或等于K.2503080209010854035252388例如:是二叉排序树。66不3BSTADT(1)//BSTimplementationfortheDictionaryADTtemplate<classKey,classElem,classKEComp,classEEComp>classBST:publicDictionary<Key,Elem,

KEComp,EEComp>{private:

BinNode<Elem>*root;//RootoftheBST

int

nodecount;//Numberofnodesvoidclearhelp(BinNode<Elem>*);

BinNode<Elem>*

inserthelp(BinNode<Elem>*,constElem&);

BinNode<Elem>*

deletemin(BinNode<Elem>*,BinNode<Elem>*&);

BinNode<Elem>*removehelp(BinNode<Elem>*,constKey&,BinNode<Elem>*&);

bool

findhelp(BinNode<Elem>*,constKey&,Elem&)const;voidprinthelp(BinNode<Elem>*,int)const;4BSTADT(2)public:BST(){root=NULL;nodecount=0;}~BST(){clearhelp(root);}voidclear(){clearhelp(root);root=NULL;

nodecount=0;}

boolinsert(constElem&e){root=inserthelp(root,e);

nodecount++;returntrue;}

boolremove(constKey&K,Elem&e){

BinNode<Elem>*t=NULL;root=removehelp(root,K,t);if(t==NULL)returnfalse;e=t->val();

nodecount--;deletet;returntrue;}5BSTADT(3)

bool

removeAny(Elem&e){//Deleteminvalueif(root==NULL)returnfalse;//Empty

BinNode<Elem>*t;root=deletemin(root,t);e=t->val();deletet;

nodecount--;returntrue;}

boolfind(constKey&K,Elem&e)const{returnfindhelp(root,K,e);}

intsize(){returnnodecount;}voidprint()const{if(root==NULL)

cout<<"TheBSTisempty.\n";elseprinthelp(root,0);}6BSTSearchtemplate<classKey,classElem,classKEComp,classEEComp>boolBST<Key,Elem,KEComp,EEComp>::

findhelp(BinNode<Elem>*subroot,constKey&K,Elem&e)const{if(subroot==NULL)returnfalse;elseif(KEComp::lt(K,subroot->val()))returnfindhelp(subroot->left(),K,e);elseif(KEComp::gt(K,subroot->val()))returnfindhelp(subroot->right(),K,e);else{e=subroot->val();returntrue;}}7BSTInsert(1)8BSTInsert(2)template<classKey,classElem,classKEComp,classEEComp>BinNode<Elem>*BST<Key,Elem,KEComp,EEComp>::

inserthelp(BinNode<Elem>*subroot,constElem&val){if(subroot==NULL)//Empty:createnodereturnnewBinNodePtr<Elem>(val,NULL,NULL);if(EEComp::lt(val,subroot->val()))

subroot->setLeft(inserthelp(subroot->left(),

val));elsesubroot->setRight(

inserthelp(subroot->right(),val));//Returnsubtreewithnodeinsertedreturnsubroot;}9RemoveMinimumValuetemplate<classKey,classElem,classKEComp,classEEComp>BinNode<Elem>*BST<Key,Elem,

KEComp,EEComp>::deletemin(BinNode<Elem>*subroot,

BinNode<Elem>*&min){if(subroot->left()==NULL){min=subroot;returnsubroot->right();}else{//Continueleft

subroot->setLeft(

deletemin(subroot->left(),min));returnsubroot;}}10BSTRemove(1)删除C或HABCDEFGHIJCNULLHNULL11BSTRemove(2)删除D或GABCDEFGHIJDG12BSTRemove(3)删除37372473224240421204140404013BSTRemove(3)14BSTRemove(4)template<classKey,classElem,classKEComp,classEEComp>BinNode<Elem>*BST<Key,Elem,KEComp,EEComp>::removehelp(BinNode<Elem>*subroot,constKey&K,BinNode<Elem>*&t){if(subroot==NULL)returnNULL;elseif(KEComp::lt(K,subroot->val()))

subroot->setLeft(

removehelp(subroot->left(),K,t));elseif(KEComp::gt(K,subroot->val()))

subroot->setRight(

removehelp(subroot->right(),K,t));15BSTRemove(5)

else{//Foundit:removeit

BinNode<Elem>*temp;t=subroot;if(subroot->left()==NULL)

subroot=subroot->right();elseif(subroot->right()==NULL)

subroot=subroot->left();else{//Bothchildrenarenon-empty

subroot->setRight(

deletemin(subroot->right(),temp));

Elemte=subroot->val();

subroot->setVal(temp->val());temp->setVal(te);

t=temp;}}returnsubroot;}16CostofBSTOper