算法之二叉树各种遍历 (二)
mpty()){
if(p != NULL){
//存入栈中
stack.push(p);
//访问根节点
printf("%c ",p->data);
//遍历左子树
p = p->lchild;
}
else{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}//while
}
/* 先序遍历(非递归)
思路：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
*/
void PreOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//访问根节点
printf("%c ",p->data);
//遍历左子树
p = p->lchild;
}
else{
//退栈
p = stack.top();
stack.pop();
//访问右子树
p = p->rchild;
}
}//while
}
<2>中序遍历
【思路】：T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
[cpp]
void InOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//遍历左子树
p = p->lchild;
}
else{
//退栈，访问根节点
p = stack.top();
printf("%c ",p->data);
stack.pop();
//访问右子树
p = p->rchild;
}
}//while
}
void InOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
//栈不空或者p不空时循环
while(p || !stack.empty()){
if(p != NULL){
//存入栈中
stack.push(p);
//遍历左子树
p = p->lchild;
}
else{
//退栈，访问根节点
p = stack.top();
printf("%c ",p->data);
stack.pop();
//访问右子树
p = p->rchild;
}
}//while
}
<3>后序遍历
【思路】：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
[cpp]
//后序遍历(非递归)
typedef struct BiTNodePost{
BiTree biTree;
char tag;
}BiTNodePost,*BiTreePost;
void PostOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
BiTreePost BT;
//栈不空或者p不空时循环
while(p != NULL || !stack.empty()){
//遍历左子树
while(p != NULL){
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
//访问过左子树
BT->tag = 'L';
stack.push(BT);
p = p->lchild;
}
//左右子树访问完毕访问根节点
while(!stack.empty() && (stack.top())->tag == 'R'){
BT = stack.top();
//退栈
stack.pop();
BT->biTree;
printf("%c ",BT->biTree->data);
}
//遍历右子树
if(!stack.empty()){
BT = stack.top();
//访问过右子树
BT->tag = 'R';
p = BT->biTree;
p = p->rchild;
}
}//while
}
//后序遍历(非递归)
typedef struct BiTNodePost{
BiTree biTree;
char tag;
}BiTNodePost,*BiTreePost;
void PostOrder2(BiTree T){
stack stack;
//p是遍历指针
BiTree p = T;
BiTreePost BT;
//栈不空或者p不空时循环
while(p != NULL || !stack.empty()){
//遍历左子树
while(p != NULL){
BT = (BiTreePost)malloc(sizeof(BiTNodePost));
BT->biTree = p;
//访问过左子树
BT->tag = 'L';
stack.push(BT);
p = p->lchild;
}
//左右子树访问完毕访问根节点
while(!stack.empty() && (stack.top())->tag == 'R'){
BT = stack.top();
//退栈