二叉排序树实验报告总结

实验报告

课程名：数据结构（C语言版） 实验名：二叉排序树 姓名： 班级： 学号：

撰写时间：2014.12.18

一 实验目的与要求

1. 掌握二叉排序树上进行插入和删除的操作 2. 利用 C 语言实现该操作 二 实验内容

? 对于一个线形表, 利用不断插入的方法, 建立起一株二叉排序树

? 从该二叉排序树中删除一个叶子节点, 一个只有一个子树的非叶子节，一个有两个子树的非叶子节点。

三 实验结果与分析

#include #include

//二叉查找树结点描述 typedef int KeyType; typedef struct Node {

KeyType key; //关键字 struct Node * left; //左孩子指针 struct Node * right; //右孩子指针 struct Node * parent; //指向父节点指针 }Node,*PNode;

//往二叉查找树中插入结点

//插入的话，可能要改变根结点的地址，所以传的是二级指针 void inseart(PNode * root,Ke

内蒙古科技大学 本科生课程设计论文 《数据结构与算法》

题 目：二叉排序树的操作 学生姓名：贺英杰 学 号：1367159108 专 业：软件工程 班 级：13-1班 指导教师：周李涌

日 期：2015年1月6日

内蒙古科技大学

内蒙古科技大学课程设计任务书

课程名称 设计题目 指导教师 周李涌 数据结构与算法课程设计 二叉排序树的操作 时间 2015.1.5——2015.1.9 一、教学要求 1. 掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力 2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 4. 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风 二、设计资料及参数 每个学生在教师提供的课程设计题目中任意选择一题，独立完成，题目选定后不可更换。 二叉排序树的操作 以二叉链表表示二叉排序树，在此基础上实现二叉排序树的操作。 要求设计类（或类模板）来描述二叉排序树，包含必要的构造函数和析构函数，以及其他能够完成如下功能的成员函数： ? 创建二叉排序树 ? 输出二叉排

二叉排序树的基本操作的实现

I.

设计要求

1. 问题描述

从磁盘读入一组数据，建立二叉排序树并对其进行查找、、遍历、插入、删除等基本操作。 2. 需求分析

建立二叉排序树并对其进行查找，包括成功和不成功两种情况。

II. 概要设计

为了实现需求分析中的功能，可以从以下3方面着手设计。 1. 主界面设计

为了方便对二叉排序树的基本操作，设计一个包含多个菜单选项的主控制子程序以实现二叉排序树的各项功能。本系统的主控制菜单运行界面如图1所示。

图1二叉排序树的基本操作的主菜单

2. 存储结构的设计

本程序主要采二叉树结构类型来表示二叉排序树。其中二叉树节点由1个表示关键字的分量组成，还有指向该左孩子和右孩子的指针。 3. 系统功能设计

本程序设置了5个子功能菜单，其设计如下。

1) 建立二叉排序树。根据系统提示，输入节点的关键字，并以0作为结束的标

识符。该功能由Bstree Create()函数实现。

2) 插入二叉排序新的节点信息。每次只能够插入一个节点信息，如果该节点已

经存在，则不插入。该功能由Bstree Insert(y)函数实现。

3) 查询二叉排序树的信息。每次进行查询，成功则显示“查询到该节点”，不成

功则“显示查询不到该节点“该功

东华理工大学理学院

课 程 设 计 报 告

——数据结构

题目：二叉排序树

姓 名： 学 号： 专 业： 班 级： 指导老师：

年数据结构课程设计

月 日

1

东华理工大学理学院

目 录

一、课程设计简介 ............................................................................ 3 二、原理分析及流程 ........................................................................ 3

2.1、原理分析............................................................................3 2.2、流程图..........................................................

山东工商学院

《数据结构》实验指导及报告书

2012 / 2013 学年

姓名： 学号： 班级： 指导教师：

Xx学院

2012年11月25日

第 一 学期

实验三 二叉树

一、实验目的

1、掌握二叉树的基本特性

2、掌握二叉树的先序、中序、后序的递归遍历算法 3、理解二叉树的先序、中序、后序的非递归遍历算法

4、通过求二叉树的深度、叶子结点数和层序遍历等算法，理解二叉树的基本特性

二、实验预习

说明以下概念

1、二叉树：是另一种树型结构，它的特点是每个结点至多只有两棵子树，并且二叉树有左右之分，其次序不能任意颠倒。 2、递归遍历：

1、 非递归遍历：

4、层序遍历：

三、实验内容和要求

1、阅读并运行下面程序，根据输入写出运行结果，并画出二叉树的形态。 #include #include

#define MAX 20

typedef struct BTNode{ /*节点结构声明*/

char data ; /*节点数据*/ struct BTNode *lchild;

struct BTNode *rchild ;

二叉排序树与平衡二叉树的实现

【摘要】

本课程设计分为两部分。第一部分为分别用二叉链表和顺序表作为存储结构实现二叉排序树，并实现树的生成，中序遍历，计算平均查找长度，对结点进行查找、删除等操作。第二部分为用二叉链表作为存储结构实现平衡二叉树，并实现树的生成，计算平均查找长度，元素的插入、删除及之后的重新平衡等操作。

【关键词】二叉排序树，平衡二叉树，中序遍历，平均查找长度 1.介绍

该设计分别采用二叉链表和顺序表作存储结构，实现对二叉排序树和平衡二叉树的以下操作：

(1)用二叉链表作存储结构实现二叉排序树。

1)以0作为输入结束标志，输入数列L，生成一棵二叉排序 树T；

2)对二叉排序树T作中序遍历，输出结果；

3)计算二叉排序树T查找成功的平均查找长度，输出结果； 4)输入元素x，查找二叉排序树T，若存在含x的结点，则删除该结点，并作中序遍历(执行操作2)；否则，输出信息“无x”； (2)用顺序表(一维数组)作存储结构实现二叉排序树。

1)以回车符(‘\\n’)为输入结束标志，输入数列L，生成一棵二叉排序树T；

34

2)对二叉排序树T作中序遍历，输出结果；

《数据结构》实验报告

◎实验题目:创建二叉排序树与查找

◎实验目的：1、掌握使用Visual C++6.0上机调试程序的基本方法；

2、掌握二叉排序树的创建和二叉排序树查找的方法。

3、提高自己分析问题和解决问题的能力，在实践中理解教材上的理论。

◎实验内容：建立至少10个顶点的二叉排序树，然后对其进行中序遍历，接着进行查找， 判断待查找数据是否存在。 一、需求分析

1、输入的形式和输入值的范围：根据提示，首先输入顶点中的数据，在进行查找操作时，输入待查找的数据，接着选择下一步要进行的操作(A.新二叉排序树;B.继续查找;C.结束操作)。

2、输出的形式：输出二叉排序的中序遍历结果，在输入待查找的数据后，输出查找的结果。 3、程序所能达到的功能：输入顶点数据后，创建二叉排序树，接着进行中序遍历，再输入待查找数据进行查找操作。 4、测试数据：

请输入顶点数据:53 25 76 20 48 14 60 84 33 78 中序遍历结果为:14 20 25 33 48 53 60 76 78 84 输入待查找数据:33 待查找数据存在

选择操作(A.新二叉排序树;B.继续查找;C.结束操作):B 输入待查找数据:54 待查找数据不存在

选择操作(

安徽新华学院

数据结构课程设计报告

题目：用顺序和二叉树存储结构实现二叉树排序 学院：信息工程 专业：信息与计算科学 班级：12信科本一班 姓名：李智 学号：1242155110 指导教师：李明 设计时间： 2013-12-16至2013-12-30

数据结构课程设计

课程设计任务书

一．设计任务

研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。

二．设计要求

（1）. 利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。

（2）. 利用顺序存储和链式存储两种算法计算实现中序遍历。

（3）. 利用顺序存储和链式存储两种算法计算实现查找结点。

（4）. 利用顺序存储和链式存储两种算法计算实现删除结

安徽新华学院

数据结构课程设计报告

题目：用顺序和二叉树存储结构实现二叉树排序 学院：信息工程 专业：信息与计算科学 班级：12信科本一班 姓名：李智 学号：1242155110 指导教师：李明 设计时间： 2013-12-16至2013-12-30

数据结构课程设计

课程设计任务书

一．设计任务

研究关于如何创建二叉排序树并对树进行遍历，查找和删除等操作，同时关注用顺序和二叉链表作存储结构带来的区别。

二．设计要求

（1）. 利用顺序存储和链式存储两种算法计算实现二叉搜索树的创建。

（2）. 利用顺序存储和链式存储两种算法计算实现中序遍历。

（3）. 利用顺序存储和链式存储两种算法计算实现查找结点。

（4）. 利用顺序存储和链式存储两种算法计算实现删除结

实验报告

一、实验目的

1、熟悉二叉树树的基本操作。

2、掌握二叉树的实现以及实际应用。

3、加深二叉树的理解，逐步培养解决实际问题的编程能力。

二、实验环境

1台WINDOWS环境的PC机，装有Visual C++ 6.0。

三、实验内容

【问题描述】 现需要编写一套二叉树的操作函数，以便用户能够方便的利用这些函数来实现自己的应用。其中操作函数包括：

1> 创建二叉树CreateBTNode(*b,*str)：根据二叉树括号表示法的字符串*str生成对应的链

式存储结构。

2> 输出二叉树DispBTNode(*b)：以括号表示法输出一棵二叉树。

3> 查找结点FindNode(*b,x)：在二叉树b中寻找data域值为x的结点,并返回指向该结点

的指针。

4> 求高度BTNodeDepth(*b)：求二叉树b的高度。若二叉树为空,则其高度为0；否则,其

高度等于左子树与右子树中的最大高度加l。 5> 求二叉树的结点个数NodesCount(BTNode *b) 6> 先序遍历的递归算法：void PreOrder(BTNode *b) 7> 中序遍历的递归算法：void InOrder(BTNode *b) 8> 后序遍历递归算法：