算法博大精深 平时就多积累点
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 野猪红 阅读(711) 评论(0)  编辑 收藏 引用 所属分类: 算法

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理