template <class Type> istream operator >>( istream &in Binary Tree<Type>& tree 重载 abstracting操作符“>”,用于输入数据元素并同时创建 棵 /叉树Tree Type item cout << Construct binary tree: n cout<< input data(end with"<< Tree. Refvalue <<" tem while( item !=Tree. RefValue Tree. Insert(iem);/将数据元素tem插入到二叉树Tree中 cout < Input dataend with"<< Tree. Refvalue<<") in > item return in 2021220
2021/2/20 16 template <class Type> istream & operator >> ( istream & in , BinaryTree<Type> & Tree ) //重载abstracting 操作符“ >> ” ，用于输入数据元素并同时创建一 棵 //二叉树Tree { Type item ; cout << “ Construct binary tree : \n ” ; cout << “ input data ( end with ” << Tree.RefValue << “ ) : ” ; in >> item ; while ( item != Tree.RefValue ) { Tree.Insert ( item ) ; //将数据元素item 插入到二叉树Tree 中 cout << “ Input data ( end with ” << Tree.RefValue << “ ) : ” ; in >> item ; } return in ; }
74二叉搜索树( Binary Search Tree)P235 定乂:一棵二叉树称之为二叉搜索树,如果它满足以下条件 它或者是空树 或者左子树中结点的关键码均小于根结点的关键码, 并且右子树中结点的关键码均大于根结点的关键码 并且左子树和右子树均为二叉搜索树。 显然,二叉搜索树的中序遍历的输出序列是一严格递增的有序序列 叉搜索数的类定义 2021220
2021/2/20 17 7.4 二叉搜索树(Binary Search Tree ) P235 定义：一棵二叉树称之为二叉搜索树，如果它满足以下条件： 它或者是空树； 或者左子树中结点的关键码均小于根结点的关键码， 并且右子树中结点的关键码均大于根结点的关键码， 并且左子树和右子树均为二叉搜索树。 显然，二叉搜索树的中序遍历的输出序列是一严格递增的有序序列 二叉搜索数的类定义：
#include iostream. h> template< class Type> class bst;∥叉搜索树类的前视声明 template <class Type> class BstNode: public BinTreeNode ∥二叉搜索树结点类的定义。二叉搜索树的结点类是一般二叉树结点 /(的公有继承 friend class bst< Type>;/叉搜索树类是二叉搜索树结点类的友元类 public BstNode() leftChild( null ) rightChild( NULL)() BstNode( const type d) data( d ), leftchild( NULL), right Child( null)i BstNode( const Type d=0, BstNode *L-NULL, BstNode x R-NULL ) data( d), leftchild( L), rightChild(r)j BstNode(i protected pe BstNode< type>* leftchild, right Child 2021220
2021/2/20 18 #include < iostream . h > template <class Type> class BST ; //二叉搜索树类的前视声明 template <class Type> class BstNode : public BinTreeNode //二叉搜索树结点类的定义。二叉搜索树的结点类是一般二叉树结点 //类的公有继承 { friend class BST<Type>;//二叉搜索树类是二叉搜索树结点类的友元类 public: BstNode( ) : leftChild( NULL ),rightChild( NULL ) { } BstNode( const Type d ) : data( d ), leftChild( NULL ) , rightChild( NULL ) { } BstNode( const Type d=0 , BstNode * L=NULL , BstNode * R=NULL ) : data( d ), leftChild( L ), rightChild( R ) { } ~BstNode( ) { } protected : Type data ; BstNode<Type> * leftChild , * rightChild ; }
Template <class Type> class bst: Binary Tree i public BSTO: root(NULL)( BST(Type value): Refvalue( value), root(NULD)&) BStOIMake Empty root); const bst& operator=( const bst& Tree void MakeEmpty( int Find( const Type &x)const f return Find(x, root)==NULL:; j Type Min() Type Max() void Insert( const Type & x)( Insert(x, root);) void remove( const Type &x) Remove( x, root);) BstNode< Type>* Split( Type i, BST<Type>& b pe &x, bst<type>&c) 2021220
2021/2/20 19 Template <class Type> class BST : BinaryTree // { public: BST ( ) : root ( NULL ) { } BST ( Type value ) : RefValue(value) , root(NULL) { } ~BST ( ) { MakeEmpty( root ) ；｝ const BST & operator = ( const BST & Tree ) ; void MakeEmpty( ) ; int Find( const Type & x ) const { return Find( x , root ) == NULL ; } Type Min( ) ; Type Max( ) ; void Insert( const Type & x ) { Insert( x , root ) ; } void Remove( const Type & x ) { Remove( x , root ) ; } BstNode<Type> * Split( Type i, BST <Type> & B , Type & x , BST<Type> & C );
private BstNode< type>*root Type revalue BstNode<Type>* lastfound void Make Empty( BstNode< Type>*& ptr) void Insert( const Type & x, bstNode< type>*& ptr void Remove(const Type &x, BstNode< type>*& ptr) BstNode< Type>* Find( const Type &x BstNode< type>* ptr )const BstNode<Type>* Min( Bstnode< type>* ptr )const BstNode< type>* max( bstNode< type>* ptr)const friend class BSTIterator< Type 2021220 20
2021/2/20 20 private: BstNode<Type> * root ; Type RefValue ; BstNode<Type> * lastfound ; void MakeEmpty( BstNode<Type> * & ptr ) ; void Insert( const Type & x , BstNode<Type> * & ptr ); void Remove(const Type & x , BstNode<Type> * & ptr ) ; BstNode<Type> * Find( const Type & x , BstNode<Type> * ptr ) const ; BstNode<Type> * Min( BstNode<Type> * ptr ) const ; BstNode<Type> * Max( BstNode<Type> * ptr ) const ; friend class BSTIterator<Type> ; }