0001 template <typename T> BinNodePosi(T) BST<T>::insert ( const T& e ) { //将关键码e插入BST树中 0002 BinNodePosi(T) & x = search ( e ); if ( x ) return x; //确认目标不存在(留意对_hot的设置) 0003 x = new BinNode<T> ( e, _hot ); //创建新节点x:以e为关键码,以_hot为父 0004 _size++; //更新全树规模 0005 updateHeightAbove ( x ); //更新x及其历代祖先的高度 0006 return x; //新插入的节点,必为叶子 0007 } //无论e是否存在于原树中,返回时总有x->data == e