#include<iostream>
#include<queue>
#include<stack>
using namespace std;
typedef char DataType;
struct Binary_node
{
DataType data;// 数据域
Binary_node* left;// 指向左子女
Binary_node* right;//指向右子女
};
typedef struct {
int tag;
Binary_node* t;
}Elem;
class Binary_tree
{
public:
Binary_tree( );//构造函数
void buildTree(void); //构造二叉树
/*遍历二叉树*/
void preorder(void);
void inorder(void);
void postorder(void);
private:
Binary_node *root;//树根
};
Binary_tree::Binary_tree( )
{
root=NULL;
};
void Binary_tree::buildTree(void)
{
queue<Binary_node*> A;
queue<Binary_node*> B;
Binary_node* tempNode=new Binary_node( );//初始化
do
{
cin>>tempNode->data;
if(tempNode->data!='#')
{
tempNode->left=NULL;
tempNode->right=NULL;
A.push(tempNode);
}
else
break;
}while(1);//输入#号结束队列输入
Binary_node* pNode=A.front( );
A.pop( );
root=pNode;//取出的第一个结点作为树根
B.push(pNode);
while(!A.empty( ))//当队列A不为空时,构造二叉树
{
Binary_node* pfather=B.front( );
B.pop( );
Binary_node* plchild=A.front( );
A.pop( );
Binary_node* prchild=A.front( );
A.pop( );
pfather->left=plchild;
pfather->right=prchild;
if(plchild!=NULL)
{
B.push(plchild);
}
if(prchild!=NULL)
{
B.push(prchild);
}
}
};
void Binary_tree::preorder( )
{
stack<Binary_node*> s;
Binary_node *t;
if(root==NULL)
return ;
t=root;
s.push(root);
while(!s.empty( ))
{
t=s.top( );
s.pop( );
if(t!=NULL)
{
cout<<t->data<<" ";
s.push(t->right);
s.push(t->left);
}
}
}
void Binary_tree::inorder( )
{
stack<Binary_node*> s;
Binary_node *c=root;
if(c==NULL)
return ;
while(c!=NULL||!s.empty( ))
{
while(c!=NULL)
{
s.push(c);
c=c->left;
}
c=s.top( );
s.pop( );
cout<<c->data<<" ";
c=c->right;
}
}
void Binary_tree::postorder( )
{
stack<Elem> s;
Elem stnode;
Binary_node *p=root;
if(root==NULL)
return ;
while(!s.empty( ))
{
while(p!=NULL)
{
stnode.t=p;
stnode.tag=1;
s.push(stnode);
p=p->left;
}
while(!s.empty( ))
{
stnode=s.top( );
s.pop( );
p=stnode.t;
if(stnode.tag==1)
{
stnode.tag=2;
s.push(stnode);
p=p->right;
break;
}
else
cout<<p->data<<" ";
}
}
}
int main( )
{
Binary_tree* tree = new Binary_tree();
tree->buildTree(); //构造二叉树
cout << "先根访问:\t";
tree->preorder();
cout << endl;
cout << "中根访问:\t";
tree->inorder();
cout << endl;
cout << "后根访问:\t";
tree->postorder();
cout<<endl;
system("pause");
return 0;
}
#include<queue>
#include<stack>
using namespace std;
typedef char DataType;
struct Binary_node
{
DataType data;// 数据域
Binary_node* left;// 指向左子女
Binary_node* right;//指向右子女
};
typedef struct {
int tag;
Binary_node* t;
}Elem;
class Binary_tree
{
public:
Binary_tree( );//构造函数
void buildTree(void); //构造二叉树
/*遍历二叉树*/
void preorder(void);
void inorder(void);
void postorder(void);
private:
Binary_node *root;//树根
};
Binary_tree::Binary_tree( )
{
root=NULL;
};
void Binary_tree::buildTree(void)
{
queue<Binary_node*> A;
queue<Binary_node*> B;
Binary_node* tempNode=new Binary_node( );//初始化
do
{
cin>>tempNode->data;
if(tempNode->data!='#')
{
tempNode->left=NULL;
tempNode->right=NULL;
A.push(tempNode);
}
else
break;
}while(1);//输入#号结束队列输入
Binary_node* pNode=A.front( );
A.pop( );
root=pNode;//取出的第一个结点作为树根
B.push(pNode);
while(!A.empty( ))//当队列A不为空时,构造二叉树
{
Binary_node* pfather=B.front( );
B.pop( );
Binary_node* plchild=A.front( );
A.pop( );
Binary_node* prchild=A.front( );
A.pop( );
pfather->left=plchild;
pfather->right=prchild;
if(plchild!=NULL)
{
B.push(plchild);
}
if(prchild!=NULL)
{
B.push(prchild);
}
}
};
void Binary_tree::preorder( )
{
stack<Binary_node*> s;
Binary_node *t;
if(root==NULL)
return ;
t=root;
s.push(root);
while(!s.empty( ))
{
t=s.top( );
s.pop( );
if(t!=NULL)
{
cout<<t->data<<" ";
s.push(t->right);
s.push(t->left);
}
}
}
void Binary_tree::inorder( )
{
stack<Binary_node*> s;
Binary_node *c=root;
if(c==NULL)
return ;
while(c!=NULL||!s.empty( ))
{
while(c!=NULL)
{
s.push(c);
c=c->left;
}
c=s.top( );
s.pop( );
cout<<c->data<<" ";
c=c->right;
}
}
void Binary_tree::postorder( )
{
stack<Elem> s;
Elem stnode;
Binary_node *p=root;
if(root==NULL)
return ;
while(!s.empty( ))
{
while(p!=NULL)
{
stnode.t=p;
stnode.tag=1;
s.push(stnode);
p=p->left;
}
while(!s.empty( ))
{
stnode=s.top( );
s.pop( );
p=stnode.t;
if(stnode.tag==1)
{
stnode.tag=2;
s.push(stnode);
p=p->right;
break;
}
else
cout<<p->data<<" ";
}
}
}
int main( )
{
Binary_tree* tree = new Binary_tree();
tree->buildTree(); //构造二叉树
cout << "先根访问:\t";
tree->preorder();
cout << endl;
cout << "中根访问:\t";
tree->inorder();
cout << endl;
cout << "后根访问:\t";
tree->postorder();
cout<<endl;
system("pause");
return 0;
}