第2个回答 推荐于2017-09-27
template <class T>
T search(BSTNode<T>* tree, const T& elemt)
{
stack<BSTNode<T>*> travStack;
BSTNode<T> *p = root; //遍历指针
BSTNode<T> *q = root; //层数看守
int num = 1;
If(p != NULL)
travStack.push(p);
while(!travStack.empty())
{
p = travStack.pop();
if(p->data != elemt)
if(p == q)
{
if(q->right != NULL)
{
q = q->right;
}
q = q->left;
num+=1;
}
else
{
cout<<"The number of piles is "<<num<<endl;
break;
}
if(p->left != NULL)
travStack.push(p->left);
if(p->right != NULL)
travStack.push(p->right);
}
}
这个是C++实现的,效率不高。主要运用的是前序遍历的方式,存取方式用的是队列;
思想:设置层数看守,看守始终在该层的最右端;按层次遍历,将该层元素从左向右加入到队列中;找到要求值就停止;本回答被提问者采纳