《数据结构》陈慧南 第07章课件.ppt

数据结构DataStructuresinC++      B- ,假定所有结点的关键字值各不相同,二叉搜索树或者是一棵空二叉树,或者是具有下列性质的二叉树:(1)若左子树不空,则左子树上所有结点的关键字值均小于根结点的关键字值;(2)若右子树不空,则右子树上所有结点的关键字值均大于根结点的关键字值;(3)左、右子树也分别是二叉搜索树。,将得到一个以关键字值递增排列的有序序列。南京邮电大学计算机学院二叉搜索树类template<classT>classBSTree:publicDynamicSet<T>{public:BSTree(){root=NULL;}ResultCodeSearch(T&x)const;ResultCodeInsert(T&x);ResultCodeRemove(T&x);protected:BTNode<T>*root;private:ResultCodeSearch(BTNode<T>*p,T&x)const;};<classT>ResultCodeBSTree<T>::Search(T&x)const{returnSearch(root,x);}南京邮电大学计算机学院template<classT>ResultCodeBSTree<T>::Search(BTNode<T>*p,T&x)const{if(!p)returnNotPresent;elseif(x<p->element)returnSearch(p->lChild,x); elseif(x>p->element)returnSearch(p->rChild,x); else{ x=p->element;ess; }}南京邮电大学计算机学院二叉搜索树搜索迭代算法template<classT>ResultCodeBSTree<T>::Search(T&x)const{ BTNode<T>*p=root;while(p)if(x<p->element)p=p->lChild; elseif(x>p->element)p=p->rChild;else{ x=p->element;ess; }returnNotPresent;}南京邮电大学计算机学院