#include <STDIO.H>
#include <STACK>
#include <QUEUE>
using namespace std;
typedef char DataType;
typedef struct Node{
DataType elem;
Node * rChild;
Node * lChild;
}*pNode;
bool creat(pNode &root){
DataType data;
scanf("%c",data);
if (data==EOF)
{
return false;
}
if (data=='#')
{
root=NULL;
}else{
root=(pNode)malloc(sizeof(struct Node));
root->elem=data;
creat(root->lChild);
creat(root->rChild);
}
return true;
}
// 前序遍历
void preOrder(pNode root){
if (root)
{
printf("%c ",root->elem);
if (root->lChild)
{
preOrder(root->lChild);
}
if (root->rChild)
{
preOrder(root->rChild);
}
}
}
// 前序遍历非递归实现
void preOrder2(pNode root){
stack<pNode> S;
pNode temp;
temp=root;
while(temp!=NULL || !S.empty()){
while(temp!=NULL){
printf("%c ",temp->elem);
S.push(temp);
temp=temp->lChild;
}
if (!S.empty())
{
temp = S.top();
S.pop();
temp=temp->rChild;
}
}
}
// 层次遍历
void levalTravel(pNode root){
queue<pNode> Q;
Q.push(root);
while (!Q.empty())
{
pNode temp=Q.front();
printf("%c ",temp->elem);
Q.pop();
if (temp->lChild)
{
Q.push(temp->lChild);
}
if (temp->rChild)
{
Q.push(temp->rChild);
}
}
}
// 中序遍历
void inOrder(pNode root){
if (root)
{
if (root->lChild)
{
inOrder(root->lChild);
}
printf("%c ",root->elem);
if (root->rChild)
{
inOrder(root->rChild);
}
}
}
// 对于任意节点P
// 1)若其左孩子不为空,则将P入栈并将P的左孩子赋值给当前的P,然后对当前
// 的P进行相同的处理
// 2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后
// 将当前的P置为栈顶结点的右孩子
// 3)直到P为NULL且栈为空则遍历结束
// 中序遍历非递归实现
void inOrder2(pNode root){
stack<pNode> S;
pNode temp;
temp=root;
while( temp!=NULL || !S.empty()){
while (temp !=NULL)
{
S.push(temp);//放入当前结点
temp = temp->lChild;//依次放入左孩子
}
if (!S.empty())
{
temp = S.top();
printf("%c ",temp->elem);
S.pop();
temp=temp->rChild;
}
}
}
void postOrder(pNode root){
if (root)
{
if (root->lChild)
{
postOrder(root->lChild);
}
if (root->rChild)
{
postOrder(root->rChild);
}
printf("%c ",root->elem);
}
}
// 思路:要保证根节点在左孩子和右孩子访问之后才能访问,
// 因此对于任一节点P,先将其入栈。
// 条件一:如果P不存在左孩子和右孩子,则可以直接访问它;
// 条件二:或者P存在左孩子和右孩子都已被访问过,则同样可以直接访问该节点。
// 若非上述两种情况,则将P的右孩子和左孩子依次入栈,这样就保证了每次取栈
// 顶元素的时候,左孩子在右孩子前面访问,左孩子和右孩子都在根结点前面被访问。
void postOrder2(pNode root){
stack<pNode> S;
// pNode temp;
// temp = root;
pNode pre;//前次访问的节点
pNode cur;//当前访问的节点
S.push(root);
pre=NULL;
while (!S.empty())
{
cur=S.top();
if ( (cur->lChild==NULL && cur->rChild==NULL) //条件一
|| ((pre!=NULL)&&( (pre==cur->lChild) || (pre==cur->rChild))) )//条件二
{
printf("%c ",cur->elem);
S.pop();
pre=cur;//保存前一个节点
}else{
if (cur->rChild)
{
S.push(cur->rChild);
}
if (cur->lChild)
{
S.push(cur->lChild);
}
}
}
}
void depthTravel(pNode root){
stack<pNode> S;
//printf("%c ",root->elem);
S.push(root);
while (!S.empty())
{
pNode temp = S.top();
printf("%c ",temp->elem);
S.pop();
if (temp->rChild)
{
S.push(temp->rChild);
}
if (temp->lChild)
{
S.push(temp->lChild);
}
}
}
int main(){
// pNode root;
// creat(root);
pNode root1=(pNode)malloc(sizeof(Node));
root1->lChild=NULL;
root1->rChild=NULL;
pNode root2=(pNode)malloc(sizeof(Node));
root2->lChild=NULL;
root2->rChild=NULL;
pNode root3=(pNode)malloc(sizeof(Node));
root3->lChild=NULL;
root3->rChild=NULL;
pNode root4=(pNode)malloc(sizeof(Node));
root4->lChild=NULL;
root4->rChild=NULL;
pNode root5=(pNode)malloc(sizeof(Node));
root5->lChild=NULL;
root5->rChild=NULL;
pNode root6=(pNode)malloc(sizeof(Node));
root6->lChild=NULL;
root6->rChild=NULL;
root1->elem='1';
root2->elem='2';
root3->elem='3';
root4->elem='4';
root5->elem='5';
root6->elem='6';
root1->lChild=root2;
root1->rChild=root3;
root2->lChild=root4;
root3->lChild=root5;
root3->rChild=root6;
printf("preOrder(root1):");
preOrder(root1);
printf("\n");
printf("preOrder2(root1):");
preOrder2(root1);
printf("\n");
printf("inOrder(root1):");
inOrder(root1);
printf("\n");
printf("levalTravel(root1):");
levalTravel(root1);
printf("\n");
printf("depthTravel(root1):");
depthTravel(root1);
printf("\n");
printf("inOrder2(root1):");
inOrder2(root1);
printf("\n");
printf("postOrder(root1):");
postOrder(root1);
printf("\n");
printf("postOrder2(root1):");
postOrder2(root1);
printf("\n");
return 0;
}