不用栈的非递归二叉树遍历 求改正 (C++新手)

Question

原程序如下，添加了双亲域parent和标志域mark；不知道哪里不对：

#include"iostream"
using namespace std;
class BinTree;

class BinNode
{
private:
int data;

BinNode *lchild;
BinNode *rchild;
BinNode *parent;
int mark;
friend class BinTree;

};

class BinTree
{
private:
BinNode *root;

public:
BinTree()
{
root=0;
}

BinNode *Get_Root()
{
    return root;
}

BinNode *Create_Tree(BinNode *r)    //先序建立二叉树
{
    int d;
    cout<<"输入数据(0代表空)：";
    cin>>d;
    if(d==0)
        return NULL;
    else
    {
        r=new BinNode;
        r->data=d;
        r->lchild=Create_Tree(r->lchild);
        r->rchild=Create_Tree(r->rchild);
    }
    root=r;
    return r;
}

void InOrder_rec1(BinNode *p)   //xian序遍历
{

    if(p)
    {
        cout<<p->data<<"  ";
        InOrder_rec1(p->lchild);
        InOrder_rec1(p->rchild);
    }
}
void InOrder_rec2(BinNode *p)   //中序遍历
{

    if(p)
    {
        InOrder_rec2(p->lchild);
        cout<<p->data<<"  ";
        InOrder_rec2(p->rchild);
    }
}


void PostOrder_rec(BinNode *p)//后续遍历
{
    BinNode*t=p;
    t->mark=0;
    while (t)
    {
        switch(t->mark){
        case 0:

            t->mark=1;
            if(t->lchild) t=t->lchild;
            break;
        case 1:
            t->mark=2;
            if(t->rchild) t=t->rchild;

        case 2:
            cout<<t->data<<endl;
            t->mark=0;
            t=t->parent;
            break;
                default:; 

        }
    }

}

};

int main()
{
BinTree tree;
BinNode *p=NULL;
p=tree.Create_Tree(p);

cout<<"先序遍历二叉树：";
tree.InOrder_rec1(p);
cout<<endl;

cout<<"中序遍历二叉树：";
tree.InOrder_rec2(p);
cout<<endl;

cout<<"中序遍历二叉树：";
tree.PostOrder_rec(p);
cout<<endl;

}

Answer 1

#include"iostream"
using namespace std;
class BinTree;

class BinNode
{
private:
    int data;

    BinNode *lchild;
    BinNode *rchild;
    BinNode *parent;
    int mark;
    friend class BinTree;
};

class BinTree
{
private:
    BinNode *root;

public:
    BinTree()
    {
        root=0;
    }

    BinNode *Get_Root()
    {
        return root;
    }

    BinNode *Create_Tree(BinNode *r)    //先序建立二叉树
    {
        int d;
        cin>>d;
        if(d==0)
            return NULL;
        else
        {
            r=new BinNode;
            r->data=d;
            r->lchild=Create_Tree(r->lchild);
            r->rchild=Create_Tree(r->rchild);
        }
        root=r;
        return r;
    }

    void InOrder_rec1(BinNode *p)   //xian序遍历
    {

        if(p)
        {
            cout<<p->data<<"  ";
            InOrder_rec1(p->lchild);
            InOrder_rec1(p->rchild);
        }
    }
    void InOrder_rec2(BinNode *p)   //中序遍历
    {

        if(p)
        {
            InOrder_rec2(p->lchild);
            cout<<p->data<<"  ";
            InOrder_rec2(p->rchild);
        }
    }


    void PostOrder_rec(BinNode *p)//后序遍历
    {

        if(p)
        {
            InOrder_rec2(p->lchild);
            InOrder_rec2(p->rchild);
            cout<<p->data<<"  ";
        }
    }
};

int main()
{
    BinTree tree;
    BinNode *p=NULL;
    cout<<"输入数据(0代表空)：";
    p=tree.Create_Tree(p);

    cout<<"先序遍历二叉树：";
    tree.InOrder_rec1(p);
    cout<<endl;

    cout<<"中序遍历二叉树：";
    tree.InOrder_rec2(p);
    cout<<endl;

    cout<<"后序遍历二叉树：";
    tree.PostOrder_rec(p);
    cout<<endl;
}