u012592941 于 2013.11.07 07:49 提问

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

}

1个回答

Benjaminzhou93   2013.11.09 14:01

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