0001 /****************************************************************************************** 0002 * Data Structures in C++ 0003 * ISBN: 7-302-33064-6 & 7-302-33065-3 & 7-302-29652-2 & 7-302-26883-3 0004 * Junhui DENG, deng@tsinghua.edu.cn 0005 * Computer Science & Technology, Tsinghua University 0006 * Copyright (c) 2003-2021. All rights reserved. 0007 ******************************************************************************************/ 0008 0009 template <typename T> BinNodePosi<T> & BST<T>::search ( const T & e ) { //在BST中查找关键码e 0010 if ( !_root || e == _root->data ) { _hot = NULL; return _root; } //空树,或恰在树根命中 0011 for ( _hot = _root; ; ) { //否则,自顶而下 0012 BinNodePosi<T> & v = ( e < _hot->data ) ? _hot->lc : _hot->rc; //确定方向,深入一层 0013 if ( !v || e == v->data ) return v; _hot = v; //一旦命中或抵达叶子,随即返回 0014 } //返回目标节点位置的引用,以便后续插入、删除操作 0015 } //无论命中或失败,_hot均指向v之父亲(v是根时,hot为NULL)