问题描述

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

原程序如下，添加了双亲域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;

}

解决方案

#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;}