11. 1 Binary search Trees 3.class bstree Program 11.1 class definition for binary search trees template<class e, class K- class BSTree: public Binary Tree<E> i public bool Search(const K&k, e& e)const BSTree<E, K>& insert(const E& e) BSTree<e, K>& delete(const K&k, E&e) void Ascendo(InOutputo; 1
11.1 Binary Search Trees 3.class BSTree Program 11.1 class definition for binary search trees template<class E, class K> class BSTree: public BinaryTree<E> { public: bool Search(const K&k, E& e)const; BSTree<E,K>& Insert(const E& e); BSTree<E,K>& Delete(const K&k,E&e); void Ascend(){InOutput();} };
11. 1 Binary search Trees BSTree is a drived class of Binary tree Indexed BS Tree may also be defined as a derived class of binary tree 1)search a binary search tree(program 11.2) template <class e, class K> bool bstree<e, K> Search(const K&k, e& e)const (//search for element that matches k pointer p starts at the root and moves through the tree looking for an element with key k
11.1 Binary Search Trees BSTree is a drived class of BinaryTree IndexedBSTree may also be defined as a derived class of BinaryTree. 1)search a binary search tree(program 11.2) template <class E,class K> bool BSTree<E,K>::Search(const K&k,E& e) const {//search for element that matches k. pointer p starts at the root and moves through the tree looking for an element with key k
11. 1 Binary search Trees Binary<>ip=root while(p)//examine p>data if(k<p>data) p=p Leftchild else if(k>p>data)p=p> Rightchild else (//found element e=p>data; return true, return false
11.1 Binary Search Trees BinaryTreeNode<E>*p=root; while(p)//examine p→data if(k<p→data) p=p→LeftChild; else if(k>p→data) p=p→RightChild; else {//found element e=p→data; return true;} return false; }
11. 1 Binary search Trees 2)Inserting into a binary search tree first verify if the element is exist in the BSTree f yes, output an error message Search for insert position and insert the element 60 Insert 35 2 80
11.1 Binary Search Trees 2)Inserting into a binary search tree • First verify if the element is exist in the BSTree if yes, output an error message. • Search for insert position,and insert the element 30 5 40 2 80 5 40 2 30 35 80 Insert 35
11. 1 Binary search Trees Program 11.3 template<class E, class K> BSTree<e, k>& bstree<e, k: Insert(const E& e) (//Insert e if not duplicate Binary TreeNodee>*p=root, *pp=0 //find place to insert while(p i pp-p
11.1 Binary Search Trees Program 11.3 template<class E,class K> BSTree<E,K>& BSTree<E,K>::Insert(const E& e) {//Insert e if not duplicate. BinaryTreeNode<E>*p=root, *pp=0; //find place to insert while(p){ pp=p;