算法博大精深 平时就多积累点
1.二叉树的非递归遍历
*先序
思想：a.根树进栈；
b.只要栈不为空 得到栈顶节点 开始循环遍历其左树 同时访问并进栈 一直到左树为空；
c.出栈直到找到有右子树的节点；
d.访问该右子树并进栈；
e.转到b步骤
大概如下：
void preOrderTravel(BinTree* t)
{
std::stack<BinTree*,std::list<BinTree*>> s;
BinTree* p=NULL;
if(!t) return;
cout<<t->data<<endl;
s.push(t);
while(!s.empty())
{
p=s.top();
while(p->left)
{
cout<<p->left->data<<endl;
s.push(p->left);
p=p->left;
}
p=s.pop();
while(!(p->right)&&!s.empty())
{
p=s.pop();
}
if(p->right)
{
cout<<p->right->data<<endl;
s.push(p->right);
}
}
}
posted on 2012-06-14 17:20
野猪红 阅读(734)
评论(0) 编辑 收藏 引用 所属分类:
算法