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

一．实验要求

二叉树的遍历操作是树形结构其他众多操作的基础。本实验旨在使学生进一步加深对二叉树的先序、中序和后序等三种遍历次序特点的理解，熟悉二叉链表存储结构，熟练掌握二叉树上的递归算法的设计技术。

二．实验题目

构造一棵二叉树，使用二叉链表方式存储，试设计程序，按照先序、中序、后序三种方式将这棵二叉树遍历出来，要求使用递归和非递归两种实现方式。

三．实现提示

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
#include
#include
#include
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 s1; //用栈存放结点
stack s2; //存放分隔符
BiTree *p,*temp;
root->data=s[0];
root->lchild=NULL;
root->rchild=NULL;
s1.push(root);
i=1;
while(i {
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<data<<"的右孩子是"< }
else
{
temp->lchild=p;
cout<data<<"的左孩子是"< }
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的左孩子是否为空，若为空，则取栈顶结点

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