数据结构----二叉树的遍历
一．实验要求
二叉树的遍历操作是树形结构其他众多操作的基础。本实验旨在使学生进一步加深对二叉树的先序、中序和后序等三种遍历次序特点的理解，熟悉二叉链表存储结构，熟练掌握二叉树上的递归算法的设计技术。
二．实验题目
构造一棵二叉树，使用二叉链表方式存储，试设计程序，按照先序、中序、后序三种方式将这棵二叉树遍历出来，要求使用递归和非递归两种实现方式。
三．实现提示
1．二叉树的线性链表存储数据结构：
[cpp]
typedef char elemtype;
typedef struct bitree{
elemtype data;
struct bitree *lchild,*rchild;
}BiTree;
2．二叉树的构造方式（参考）：
[cpp]
BiTree *create()
{
BiTree *q[100]; //定义q数组作为队列存放二叉链表中结点,100为最//大容量
BiTree *s; //二叉链表中的结点
BiTree *root ; //二叉链表的根指针
int front=1,rear=0; //定义队列的头、尾指针
char ch; //结点的data域值
root=NULL;
cin>>ch;
while(ch!='#') //输入值为#号,算法结束
{ s=NULL;
if(ch!=',') //输入数据不为逗号,表示不为虚结点,否则为虚结点
{ s=new BiTree;
s->data=ch;
s->lchild=NULL;
s->rchild=NULL;
}
rear++;
q[rear]=s; //新结点或虚结点进队
if(rear==1)
root=s;
else
{ if((s!=NULL)&&(q[front]!=NULL))
{ if(rear%2==0)
q[front]->lchild=s; //rear为偶数,s为双亲左孩子
else
q[front]->rchild=s;//rear为奇数,s为双亲右孩子
}
if(rear%2==1) front++; //出队
}
cin>>ch;
}
return root;
}
四．思考及选做
1．本实验给出了建立二叉树的二叉链表存储结构的一种方法，是否还有更简单的方法？
2．对于非递归先序遍历一般需要对每个结点进行二次进栈，这就需要一个标志位，如何处理这个标志位，使得既不需要构造新的存储结构也不需要增加一个新的标志栈。
五．我的实现
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include <iostream>
#include<stack>
using namespace std;
/*******************数据结构的定义*************************/
typedef char elemtype;
typedef struct bitree
{
elemtype data;
struct bitree *lchild,*rchild;
}BiTree;
/**********************功能函数*******************************/
/*
建树. 输入格式为: a(b,c(d,e))
*/
BiTree *create(char *s,BiTree *&root)
{
int i;
bool isRight=false;
stack<BiTree*> s1; //用栈存放结点
stack<char> s2; //存放分隔符
BiTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i<strlen(s))
{
if(s[i]=='(')
{
s2.push(s[i]);
isRight=false;
}
else if(s[i]==',')
{
isRight=true;
}
else if(s[i]==')')
{
s1.pop();
s2.pop();
}
else if(isalpha(s[i]))
{
p=(BiTree *)malloc(sizeof(BiTree));
p->data=s[i];
p->lchild=NULL;
p->rchild=NULL;
temp=s1.top();
if(isRight==true)
{
temp->rchild=p;
cout<<temp->data<<"的右孩子是"<<s[i]<<endl;
}
else
{
temp->lchild=p;
cout<<temp->data<<"的左孩子是"<<s[i]<<endl;
}
if(s[i+1]=='(')
s1.push(p);
}
i++;
}
}
/*
递归打印函数 。
*/
void display(BiTree *root)
{
if(root!=NULL)
{
printf("%c",root->data);
if(root->lchild!=NULL)
{
printf("(");
display(root->lchild);
}
if(root->rchild!=NULL)
{
printf(",");
display(root->rchild);
printf(")");
}
}
}
/*
先序遍历。递归 。
*/
void preOrder1(BiTree *root)
{
if(root!=NULL)
{
printf("%c ",root->data);
preOrder1(root->lchild);
preOrder1(root->rchild);
}
}
/*
先序遍历。非递归 。
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
*/
void preOrder2(BiTree *root)
{
stack<BiTree*> s; //也可以用数组来实现
BiTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout<<p->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<BiTree*> 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<<p->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<BiTree*> 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<<cur->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;
}
