数据结构----二叉树的遍历 - c++编程基础

并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
*/
void preOrder2(BiTree *root)
{
stack s; //也可以用数组来实现
BiTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<data<<" ";
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p->rchild;
}
}
}

/*
中序遍历。递归。
*/
void inOrder1(BiTree *root)
{
if(root!=NULL)
{
inOrder1(root->lchild);
printf("%c ",root->data);
inOrder1(root->rchild);
}
}

/*
中序遍历。非递归。
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束;
*/
void inOrder2(BiTree *root)
{
stack s;
BiTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p->lchild;
}
if(!s.empty())
{
p=s.top();
cout<data<<" ";
s.pop();
p=p->rchild;
}
}
}

/*
后序遍历。递归。
*/
void postOrder1(BiTree *root)
{
if(root!=NULL)
{
postOrder1(root->lchild);
postOrder1(root->rchild);

printf("%c ",root->data);
}
}

/*
后序遍历。非递归。
要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
如果P不存在左孩子和右孩子，则可以直接访问它；或者P存在左孩子或者右孩子，但
是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。若非上述两种情况，
则将P的右孩子和左孩子依次入栈，这样就保证了每次取栈顶元素的时候，左孩子在右孩
子前面被访问，左孩子和右孩子都在根结点前面被访问。
*/
void postOrder2(BiTree *root)
{
stack s;
BiTree *cur; //当前结点
BiTree *pre=NULL; //前一次访问的结点
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<data<<" "; //如果当前结点没有孩子结点或者孩子节点都已被访问过
s.pop();
pre=cur;
} www.2cto.com
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}

}

/***********************main函数*************************/
int main()
{
char s[100];
while((scanf("%s",s)))
{
BiTree *root=(BiTree *)malloc(sizeof(BiTree));
create(s,root);
printf("\n");
printf("先序递归遍历:");
preOrder1(root);
printf("\n");
printf("中序递归遍历:");
inOrder1(root);
printf("\n");
printf("后序递归遍历:");
postOrder1(root);
printf("\n");
printf("\n");
printf("先序非递归遍历:");
preOrder2(root);
printf("\n");
printf("中序非递归遍历:");
inOrder2(root);
printf("\n");
printf("后序非递归遍历:");
postOrder2(root);
printf("\n\n");

}

return 0;
}

数据结构----二叉树的遍历(二)