实验（三）
实验名称
二叉树的遍历
软件环境
Windows98/2000, VC++6.0或turbo C
硬件环境
PⅡ以上微型计算机
实验目的 理解二叉树的逻辑特点，掌握二叉链表存储结构，掌握二茬树遍历算法的递归与非递归实现
实验内容（应包括实验题目、实验要求、实验任务等）
二叉树的遍历
利用二叉链表作为存储结构建立一棵二叉树，每个结点中存放一种水果名(例如apple、orange、banana等，并要求从键盘输入)，结点数不少于5个。要求分别以先序、中序和后序进行遍历，输出遍历结果。并编写一递归算法，交换该二叉树中所有结点的左、右孩子。
实验过程与实验结果（可包括实验实施的步骤、算法描述、流程、结论等）
实验步骤及算法描述和流程：
1. 创建二叉链表的结点存储结构及数据的输入输出函数
因为每个结点所存储的数据类型为字符串，却无法使用字符串和String等数据类型，所以使用单链表作为结点所存储的数据类型。
1.1 数据的输入函数indata( )
当输入的字符不为'0'时，以尾插法将数据插入单链表。
1.2 数据的输出函数
直接输出单链表。
2. 生成二叉链表
利用先序遍历生成二叉链表：
2.1 用单链表s记录输入的数据
2.2 若单链表s为空，则二叉链表结点为空，否则根节点=s，利用递归调用分别生成根节点的左子树和右子树
2.3 返回二叉链表
3. 先序遍历、中序遍历、后序遍历二叉链表
3.1 先序遍历：访问根节点，左子树，右子树的顺序
3.2 中序遍历：访问左子树，根节点，右子树的顺序
3.3 后序遍历：访问左子树，右子树，根节点的顺序
利用递归调用分别用以上三种顺序遍历二叉链表。
4. 交换二叉链表的左右孩子
当二叉链表的结点左孩子或者右孩子都不为空时，利用递归调用，分别交换左子树很右孩子的左右孩子，最后将根节点的左右孩子指针交换。
5. 主函数
5.1 调用生成二叉链表的函数，从键盘输入二叉链表的各个结点
5.2 分别调用先序遍历、中序遍历、后序遍历二叉链表函数，输出所有结点
5.3 交换二叉链表的左右孩子
5.4 重复5.2
结论：
输入各个结点：apple、pear、orange、banana、peach、grape、watermelon
先序遍历输入与输入一致
中序遍历输出：orange、pear、banana、apple、grape、peach、watermelon
后序遍历输出：orange、banana、pear、grape、watermelon、peach、apple
交换二叉树的左右孩子后
先序遍历输出：apple、peach、watermelon、grape、pear、banana、orange
编程中出现的问题：
输入的二叉链表左右子树必须对称，如果不对称，交换二叉树的左右子树后，程
序出错，不知道出错在哪，没有
调试成功。
附录（可包括源程序清单或其它说明）
#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<string>
using namespace std;
typedef struct LNode{ //二叉链表数据存储结构
char data;
struct LNode *next;
}LNode,*LinkList;
typedef struct BiTNode{ //二叉链表节点存储结构
LinkList data;
struct BiTNode *lchild;
struct BiTNode *rchild; //左右孩子指针
}BiTNode,*BiTree;
void outdata(LinkList L){ //输出数据
LinkList p;
p=L->next;
while(p!=NULL){
cout<<p->data;
p=p->next;
}
cout<<" ";
}
LinkList indata(){ //输入数据
LinkList L,p,r;
char x;
r=L=(LinkList)malloc(sizeof(LNode));
L->next=NULL;
cin>>x;
while(x!='0'){
p=(LinkList)malloc(sizeof(LNode));
p->data=x;
p->next=NULL;
r->next=p;
r=p;
cin>>x;
}
return L;
}
BiTree CreateBiTree(BiTree &T){//先序遍历生成二叉树
LinkList s=indata();
if(s->next==NULL) T=NULL;
else{
T=(BiTNode*)malloc(sizeof(BiTNode));
if(!T)
exit(1);
T->data=s;
CreateBiTree(T->lchild); //建立左子树
CreateBiTree(T->rchild); //建立右子树
}
return T;
}
void PreOrder(BiTree root){ //先序遍二叉树
if(root==NULL) return;
outdata(root->data);
PreOrder(root->lchild);
PreOrder(root->rchild);
}
void InOrder(BiTree root){ //中序遍历二叉树
if(root==NULL) return;
InOrder(root->lchild);
outdata(root->data);
InOrder(root->rchild);
}
void PostOrder(BiTree root){ //后序遍历二叉树
if(root==NULL) return;
PostOrder(root->lchild);
PostOrder(root->rchild);
outdata(root->data);
}
void exchange(BiTree &root){ //交换二叉树的左右孩子
BiTree temp;
if(root->lchild!=NULL||root->rchild!=NULL){
exchange(root->lchild);
exchange(root->rchild);
temp=root->lchild;
root->lchild=root->rchild;
root->rchild=temp;
}
}
void main(){
BiTree T;
cout<<"请输入水果名作为数的每个节点，空节点请输入0，每个单词后以0结尾"<<endl;
CreateBiTree(T);
cout<<"先序遍历二叉树：";
PreOrder(T);
cout<<endl<<"中序遍历二叉树：";
InOrder(T);
cout<<endl<<"后序遍历二叉树：";
PostOrder(T);
cout<<endl<<"交换二叉树的左右孩子";
exchange(T);
cout<<endl<<"先序遍历二叉树：";
PreOrder(T);
cout<<endl<<"中序遍历二叉树：";
InOrder(T);
cout<<endl<<"后序遍历二叉树：";
PostOrder(T);
cout<<endl;
}
运行结果：
??
??
??
??
计算机科学与工程系
2
计算机科学与工程系