数据结构实验五(二叉树的建立及遍历)题目和源程序[精品].doc
文本预览下载声明
实验5:二叉树的建立及遍历
(第十三周星期三7、8节)
一 、实验目的
1.学会实现二叉树结点结构和对二叉树的基本操作。
2.掌握对二叉树每种操作的具体实现,学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。
二 、实验要求
1.认真阅读和掌握和本实验相关的教材内容生成二叉树,并/*----------------------------------------
* 05-1_递归遍历二叉树.cpp -- 递归遍历二叉树的相关操作
* 对递归遍历二叉树的每个基本操作都用单独的函数来实现
* 水上飘 2009年写
----------------------------------------*/
// ds05.cpp : Defines the entry point for the console application.
//
#include stdafx.h
#include iostream
typedef char ElemType;
using namespace std;
typedef struct BiTNode {
ElemType data;
//左右孩子指针
BiTNode *lchild, *rchild;
}BiTNode, *BiTree;
//动态输入字符按先序创建二叉树
void CreateBiTree(BiTree T) {
char ch;
ch = cin.get();
if(ch == ) {
T = NULL;
}
else {
if(ch == \n) {
cout 输入未结束前不要输入回车,
要结束分支请输入空格! endl;
}
else {
//生成根结点
T = (BiTNode * )malloc(sizeof(BiTNode));
if(!T)
cout 内存分配失败! endl;
T-data = ch;
//构造左子树
CreateBiTree(T-lchild);
//构造右子树
CreateBiTree(T-rchild);
}
}
}
//输出e的值
ElemType PrintElement(ElemType e) {
cout e ;
return e;
}
//先序遍历
void PreOrderTraverse(BiTree T) {
if (T != NULL) {
//打印结点的值
PrintElement(T-data);
//遍历左孩子
PreOrderTraverse(T-lchild);
//遍历右孩子
PreOrderTraverse(T-rchild);
}
}
//中序遍历
void InOrderTraverse(BiTree T) {
if (T != NULL) {
//遍历左孩子
InOrderTraverse(T-lchild);
//打印结点的值
PrintElement(T-data);
//遍历右孩子
InOrderTraverse(T-rchild);
}
}
//后序遍历
void PostOrderTraverse(BiTree T) {
if (T != NULL) {
//遍历左孩子
PostOrderTraverse(T-lchild);
//遍历右孩子
PostOrderTraverse(T-rchild);
//打印结点的值
PrintElement(T-data);
}
}
//按任一种遍历次序输出二叉树中的所有结点
void TraverseBiTree(BiTree T, int mark) {
if(mark == 1) {
//先序遍历
PreOrderTraverse(T);
cout endl;
}
else if(mark == 2) {
//中序遍历
InOrderTraverse(T);
cout endl;
}
else if(mark == 3) {
//后序遍历
PostOrderTraverse(T);
cout endl;
}
else cout 选择遍历结束! endl;
}
//输入值并执行选择遍历函数
void ChoiceMark(BiTree T) {
int mark = 1;
cout 请输入,先序遍历为1,中序为2,后序为3,跳过此操作为0:;
cin mark;
if(mark 0 mark 4) {
TraverseB
显示全部