第1页 / 共6页
第2页 / 共6页
第3页 / 共6页
第4页 / 共6页
第5页 / 共6页
第6页 / 共6页
数据结构实验报告6-树-二叉树的遍历算法-实验内容及要求.docx
数据结构实验报告
学号：xxxxxxxxxxx
知识范畴：树
姓名：xxxxxx
专业：计算机科学与技术
完成日期：2019 年 04 月 22 日
实验题目：二叉树的遍历算法
实验内容及要求：
评分
满分——5 分
编写程序，用先序递归遍历法建立二叉树的二叉链表存储结构，然后输出其先序、中序、
后序以及层次遍历结点访问次序。其中层次遍历的实现需使用循环队列。二叉树结点数据类型
建议选用字符类型。
实验目的：掌握二叉树的遍历算法。
数据结构设计简要描述：
建立结构体，每个结构体包含两个指针域和一个数据域，两个指针域分别指向左二子和右
儿子；结点数据类型建议选用字符类型。
算法设计简要描述：
用先序递归遍历法建立二叉树的二叉链表存储结构，然后输出其先序、中序、后序以及层
次遍历结点访问次序。其中层次遍历的实现需使用循环队列。
输入/输出设计简要描述：
输入创建二叉树的字符，空节点使用“#”占位；输出的是由先序、中序、后序以及层次
遍历结点访问的结果。
编程语言说明：
使用 Visual C++编程。主要代码采用 C 语言实现 ；动态存储分配采用 C++的 new 和 delete
操作符实现；输入与输出采用 C++的 cin 和 cout 流；程序注释采用 C/C++规范。
// 用先序遍历算法建立二叉树
主要函数说明：
BiTree CrtBT();
void preorder(const BiTree bt);
void midorder(const BiTree bt);
void lasorder(const BiTree bt);
int LayerTraval(BiTree bt);
int initQueue(BiTreeQueue bt_queue);
int enQueue(const BiTreeQueue Q,BiTree bt); // 二叉树节点入队
// 判断队列是否为空
int isEmpty(const BiTreeQueue Q);
BiTree delQueue(const BiTreeQueue Q);
// 队头元素出队
// 访问节点数据域
void visit(const BiTree bt);
// 用先序遍历算法遍历二叉树
// 用中序遍历算法遍历二叉树
// 用后序遍历算法遍历二叉树
// 层次遍历二叉树
// 初始化循环队列
1 / 6
程序测试简要报告：
源程序代码：
// CreateBinaryTree.cpp
#include "Predefine.h"
// 用先序遍历算法建立二叉树
BiTree CrtBT()
{
char ch = getchar();
if(ch=='#') // 输入#字符表示 NULL 指针域
return NULL;
BiTree bt = new BiTreeNode();
bt->data = ch;
bt->lelf_child = CrtBT();
// 建立左子树
bt->right_child = CrtBT(); // 建立右子数
return bt;
}
}
// DelQueue.cpp
#include "Predefine.h"
// 队头元素出队
BiTree delQueue(const BiTreeQueue Q)
{
if(Q->f==Q->r)
{
return NULL;
}
Q->f = (Q->f + 1)%30;
BiTree q = new BiTreeNode;
q = &Q->Node[Q->f]; // 队头元素出队
return q;
// InitQueue.cpp
#include "Predefine.h"
// 初始化循环队列
int initQueue(BiTreeQueue bt_queue)
{
bt_queue->Node = new BiTreeNode[30];
bt_queue->f = bt_queue->r = -1;
return 1; // 队列初始化成功返回 1
2 / 6
}
// IsEmpty.cpp
#include "Predefine.h"
// 判断队列是否为空
int isEmpty(const BiTreeQueue Q)
{
if(Q->f==Q->r)
{
return 1; // 队列为空返回 1
return 0; // 队列不空返回 0
}
else
{
}
}
if(bt)
{
}
}
// LasorderBinaryTree.cpp
#include "Predefine.h"
extern void visit(const BiTree bt);
// 用后序遍历算法遍历二叉树
void lasorder(const BiTree bt)
{
lasorder(bt->lelf_child);
lasorder(bt->right_child);
visit(bt);
// LayerorderBinaryTree.cpp
#include "Predefine.h"
#include "QueuePredefine.h"
extern int initQueue(BiTreeQueue bt_queue);
extern int enQueue(const BiTreeQueue Q,BiTree bt);
extern int isEmpty(const BiTreeQueue Q);
extern BiTree delQueue(const BiTreeQueue Q);
extern void visit(const BiTree bt);
// 层次遍历二叉树
int LayerTraval(BiTree bt)
{
if(bt==NULL)
{
return 0;
}
3 / 6
BiTreeQueue Q = new BiTreeNodeQueue;
initQueue(Q);
enQueue(Q,bt);
while(!isEmpty(Q))
{
bt = delQueue(Q); // 队头元素出队
visit(bt);
if(bt->lelf_child)
{
enQueue(Q, bt->lelf_child);
}
if(bt->right_child)
{
enQueue(Q, bt->right_child);
}
}
return 0;
}
// main.cpp
#include "Predefine.h"
extern BiTree CrtBT();
extern void preorder(const BiTree bt);
extern void midorder(const BiTree bt);
extern void lasorder(const BiTree bt);
extern int LayerTraval(BiTree bt);
int main()
{
BiTree bt = CrtBT();
preorder(bt);
std::cout << std::endl;
midorder(bt);
std::cout << std::endl;
lasorder(bt);
std::cout << std::endl;
LayerTraval(bt);
std::cout << std::endl;
return 0;
}
// MidorderBinaryTree.cpp
#include "Predefine.h"
extern void visit(const BiTree bt);
// 用中序遍历算法遍历二叉树
void midorder(const BiTree bt)
{
if(bt)
4 / 6
midorder(bt->lelf_child);
visit(bt);
midorder(bt->right_child);
{
}
}
// VisitBinaryTree.cpp
#include "Predefine.h"
// 访问节点数据域
void visit(const BiTree bt)
{
if(bt)
std::cout << bt->data;
}
// Predefine.h
#ifndef _PREDEFINE_H_
#define _PREDEFINE_H_
#include
#include
#include
typedef char ElemTp;
typedef struct node{
ElemTp data;
struct node *lelf_child,
// 数据域
// 左指针
*right_child;
// 右指针
}*BiTree, BiTreeNode;
typedef struct Queue{
BiTree Node; // 数据域
int f; // 队头指针
int r; // 队尾指针
}*BiTreeQueue, BiTreeNodeQueue;
#endif // _PREDEFINE_H_
// PushQueue.cpp
#include "Predefine.h"
// 二叉树节点入队
int enQueue(const BiTreeQueue Q,BiTree bt)
{
if((Q->r+1)%30==(Q->f+30)%30)
{
return 0;
}
Q->r = (Q->r+1)%30;
Q->Node[Q->r] = *bt;
5 / 6
return 1; // 入队成功返回 1
}
// PreorderBinaryTree.cpp
#include "Predefine.h"
extern void visit(const BiTree bt);
// 用先序遍历算法遍历二叉树
void preorder(const BiTree bt)
{
visit(bt);
preorder(bt->lelf_child);
preorder(bt->right_child);
if(bt)
{
}
}
6 / 6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
