中文XML论坛--张铭《数据结构与算法》书中三个非递归周游二叉树算法的改进

贴子主题：张铭《数据结构与算法》书中三个非递归周游二叉树算法的改进

本主题类别:

觉得书中的算法结构不是很明晰，自己改进了一下。算法在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();
        }
    }
}


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