以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  张铭《数据结构与算法》书中三个非递归周游二叉树算法的改进  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=36560)

--  作者：chyl
--  发布时间：8/8/2006 10:26:00 PM

--  张铭《数据结构与算法》书中三个非递归周游二叉树算法的改进
觉得书中的算法结构不是很明晰，自己改进了一下。算法在C++下编译成功。
为比较常用的回溯结构，尤其是第三个算法，个人认为比书上那个清楚很多呵呵。
希望大家多提意见，共同进步。
一、前序周游
void BinaryTree::PreOrderWithoutRecursion(BinaryTreeNode* root){
    BinaryTreeNode *p;
    p=root;
    Stack *s=new Stack(20);
    while(1){
        if(p){
            p->visit();
            s->push(p);
            p=p->leftchild();
        }
        else{
            if(s->isEmpty()) return;
            p=s->getTop();
            s->pop();
            p=p->rightchild();
        }
    }
}

二、中序周游
void BinaryTree::InOrderWithoutRecursion(BinaryTreeNode* root){
    BinaryTreeNode *p;
    p=root;
    Stack *s=new Stack(20);
    while(1){
        if(p){
            s->push(p);
            p=p->leftchild();
        }
        else{
            if(s->isEmpty()) return;
            p=s->getTop();
            s->pop();
            p->visit();
            p=p->rightchild();
        }
    }
}

三、
void BinaryTree::PostOrderWithoutRecursion(BinaryTreeNode* root){
    BinaryTreeNode *p;
    p=root;
    Stack *s=new Stack(20);
    while(1){
        if(p){
            if(p->id==2){                    //p->id==2表示该点已经周游右子树
                p->visit();
                p=0;
            }
            else{
                s->push(p);
                if(p->id==0){                //表示该点未周游任何子树
                    p->id=1;
                    p=p->leftchild();
                }
                else if(p->id==1){          //表示该点已周游左子树
                    p->id=2;
                    p=p->rightchild();
                }
            }                
        }
        else{
            if(s->isEmpty()) return;
            p=s->getTop();
            s->pop();
        }
    }
}

--  作者：Supremgoooo
--  发布时间：8/9/2006 9:24:00 AM

--  
不错不错，第3个最好了！
W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
 46.875ms