第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
数据结构实验报告7-树-二叉树的字符图形显示程序(半期测试)-实验内容与要求.docx
数据结构实验报告
学号：xxxxxxxxxxx
知识范畴：树
姓名：xxxxxx
专业：计算机科学与技术
完成日期：2019 年 05 月 06 日
实验题目：二叉树的字符图形显示程序(半期测试)
实验内容及要求：
评分
满分——10 分
设二叉树采用二叉链表存储结构，结点数据域为字符类型。编写控制台应用程序采用先序
遍历法建立二叉树存储结构并实现二叉树的字符图形显示。输入及输出示例如下：
输入: ABDH##I##EJ##K##CFL##M##GN##O##
输出:
(#表示 NULL 指针域，表示回车键)
行 1
行 2 横线由至少 2 个下划线字符组成，竖线是一个|字符
行 3
行 4
____|____ 行 5
| 行 6
|
F
G 行 7
__|__ 行 8
| 行 9
|
N
O 行 10
(行 8 的每根水平线由 2 个下划线字符组成)
__|__
|
|
L
M
A
________|________
|
|
B
C
____|____
|
|
D
E
__|__
|
|
J
K
__|__
|
|
H
I
输入: A#B#C##
输出:
A
|____
|
B
|__
|
C
输入: AB#DE##F##CG###
输出:
A
________|________
|
|
B
C
____|
|____
|
|
D
G
__|__
|
|
E
F
输入: AB##C##
输出:
A
__|__
|
|
B
C
实验目的：对于二叉树（二叉链表）存储结构，综合运用所学知识，通过分析及算法设计解决
课堂及教材未讲过的问题。
1 / 10
数据结构设计简要描述：
采用含有左、右儿子指针和数据域的结构体构成二叉树存储节点；输出树形二叉树的时候
采用 vector 容器存储满二叉树节点，不存在的节点使用“#”作为占位符。
算法设计简要描述：
使用先序遍历建立二叉树，使用层次遍历建立输出树形二叉树的间接容器。
输入/输出设计简要描述：
输入先序建立二叉树的字符序列；
输出树形二叉树。
编程语言说明：
使用 Code::Blocks 编程。 主要代码采用 C++语言实现 ；动态存储分配采用 C++的 new 和
delete 操作符实现；输入与输出采用 C++的 cin 和 cout 流；程序注释采用 C/C++规范。
// 用先序遍历算法建立二叉树
主要函数说明：
BiTree CrtBT()
BiTree delQueue(const BiTreeQueue Q)
int initQueue(BiTreeQueue bt_queue)
int isEmpty(const BiTreeQueue Q)
int LayerTraval(BiTree bt) // 层次遍历二叉树，求得按照层次存放的满二叉树数组
void printTree(std::vector tree)
int enQueue(const BiTreeQueue Q,BiTree bt)
// 将二叉树按照树形输出
// 二叉树节点入队
// 队头元素出队
// 初始化循环队列
// 判断队列是否为空
程序测试简要报告：
2 / 10
源程序代码：
// 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"
// 队头元素出队
3 / 10
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
}
// IsEmpty.cpp
#include "Predefine.h"
// 判断队列是否为空
int isEmpty(const BiTreeQueue Q)
{
if(Q->f==Q->r)
{
return 1; // 队列为空返回 1
}
else
{
}
}
return 0; // 队列不空返回 0
// LayerorderBinaryTree.cpp
#include "Predefine.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);
extern std::vector List;
// 层次遍历二叉树
4 / 10
int LayerTraval(BiTree bt)
{
if(bt==NULL)
{
return 0;
}
BiTreeQueue Q = new BiTreeNodeQueue;
initQueue(Q);
enQueue(Q,bt);
List.insert(List.end(),bt->data); // 按照层次顺序存放在 vector 容器中
while(!isEmpty(Q))
{
bt = delQueue(Q); // 队头元素出队
// 如果取出的节点是占位符，则容器中进入两个占位符儿子节点
if(bt->data=='#')
{
List.insert(List.end(),'#');
List.insert(List.end(),'#');
continue;
}
if(bt->lelf_child)
{
enQueue(Q, bt->lelf_child);
// 左儿子进入容器
List.insert(List.end(),bt->lelf_child->data);
}
else{
// 队列中进入占位符节点，并且容器中进两个占位符
BiTree node = new BiTreeNode;
node->data = '#';
enQueue(Q, node);
List.insert(List.end(),'#');
}
if(bt->right_child)
{
enQueue(Q, bt->right_child);
// 右儿子进入容器
List.insert(List.end(),bt->right_child->data);
}
else{
// 队列中进入占位符节点，并且容器中进两个占位符
BiTree node = new BiTreeNode;
node->data = '#';
enQueue(Q, node);
List.insert(List.end(),'#');
}
}
5 / 10
return 0;
}
// main.cpp
#include "Predefine.h"
extern BiTree CrtBT();
extern int LayerTraval(BiTree bt);
extern void printTree(std::vector tree);
std::vector List;
int main()
{
BiTree bt = CrtBT();
LayerTraval(bt);
std::cout << std::endl;
printTree(List);
return 0;
}
// Predefine.h
#ifndef _PREDEFINE_H_
#define _PREDEFINE_H_
#include
#include
#include
#include
#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_
// PrintTree.cpp
#include "Predefine.h"
extern int g_nCount;
extern std::vector List;
6 / 10
// 将二叉树按照树形输出
void printTree(std::vector tree)
{
int tree_size = tree.size();// 树的节点数目
if(!tree_size)
{
exit(0);
// 每一行的起始位置
// 两个"|"之间的空格数
}
int size_format[5] = {40,30,25,22,21};
int size_space[5] = {40,20,10,4,3};
std::string symbol[5] = {"____________________","__________","_____","___","_"}; // 树的形状控制符
int size_interval[5] = {20,10,5,3,1};
int layer_number = log(tree_size+1)/log(2); // 记录树的层数
std::cout << std::setw(61) << List.at(0) << std::endl;// 输出第一层
int number = 1; // 记录已经被访问的节点数
int *dp = new int[128];
// std::cout << layer_number <
std::cout << std::setw(size_interval[i-2]-1) << " ";
std::cout << std::setw(size_space[i-2]) << " ";
continue;
}
// 上个节点有右儿子的格式
else if(dp[k])
{
std::cout << std::setw(size_interval[i-2]) << " ";
std::cout << "|"+symbol[i-2];
std::cout << std::setw(size_space[i-2]-1) << " ";
continue;
}
// 上个节点没儿子的格式
else{
std::cout << std::setw(size_interval[i-2]*2) << " ";
std::cout << std::setw(size_space[i-2]-1) << " ";
}
}
std::cout << std::endl; // 输出一行所有符号之后光标换到下一行
/***************************************************************
以下的循环都是为了控制二叉树的格式，代码注释与上面循环类似
**************************************************************/
// 输出二叉树节点顶部的"|"符号
std::cout << std::setw(size_format[i-2])<<' ';
for(int j=1;j<=pow(2,i-1);j+=2)
{
if(dp[j-1] && dp[j])
{
std::cout << "|";
std::cout << std::setw(size_interval[i-2]*2-1) << " ";
std::cout << "|";
std::cout << std::setw(size_space[i-2]-1) << " ";
continue;
}
else if(dp[j-1])
{
std::cout << "|";
std::cout << std::setw(size_interval[i-2]*2-1) << " ";
std::cout << std::setw(size_space[i-2]-1) << " ";
continue;
}
else if(dp[j])
{
std::cout << std::setw(size_interval[i-2]*2) << " ";
std::cout << "|";
8 / 10
相关推荐
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
