数据结构与算法实验报告二叉树遍历

数据结构上机实验报告

二叉树问题

陈冠豪

2010210501

0101015

二O一O年5月26号

验的目建一棵立二树叉要，分别求递用归和递非方法实归二现 叉树的先、序序中和序遍后历。

实现代码:

#ifndef TREE_H #define TREE_H #include <stdio.h> #include <malloc.h> #include <stack> #include <queue> #include <assert.h> using namespace std; typedefintElemType; typedef struct treeT { ElemType key; struct treeT* left; struct treeT* right; }treeT, *pTreeT;

static void visit(pTreeT root) { if (NULL != root) { printf(" %d\n", root->key); } } static pTreeT BT_MakeNode(E

实验六：二叉树及其应用

一、实验目的

树是数据结构中应用极为广泛的非线性结构，本单元的实验达到熟悉二叉树的存储结构的特性，以及如何应用树结构解决具体问题。

二、问题描述

首先，掌握二叉树的各种存储结构和熟悉对二叉树的基本操作。其次，以二叉树表示算术表达式的基础上，设计一个十进制的四则运算的计算器。 如算术表达式：a+b*(c-d)-e/f

三、实验要求

如果利用完全二叉树的性质和二叉链表结构建立一棵二叉树，分别计算统计叶子结点的个数。求二叉树的深度。十进制的四则运算的计算器可以接收用户来自键盘的输入。由输入的表达式字符串动态生成算术表达式所对应的二叉树。自动完成求值运算和输出结果。

四、实验环境

PC微机

DOS操作系统或 Windows 操作系统

Turbo C 程序集成环境或 Visual C++ 程序集成环境 1、根据二叉树的各种存储结构建立二叉树；

2、设计求叶子结点个数算法和树的深度算法；

3、根据表达式建立相应的二叉树，生成表达式树的模块； 4、根据表达式树，求出表达式值，生成求值模块； 5、程序运行效果，测试数据分析算法。

五、实验步骤

六、测试数据

1、输入数据：2.2*（3.1+1.20）-7.5/3

正确结果：6.9

数据结构实验报告

题目：平衡二叉树

学 院 专 业 年级班别 学 号 学生姓名 指导教师

2015年7月1日

1.题目：采用字符类型为整型类型和链式存储结构，实现抽象数据类型BTree。 ADT BTree{

数据对象：D＝{ai | ai∈ElemSet, i=1,2,...,n, n≥0 } 数据关系：R1＝{ |ai-1, ai∈D, i=2,...,n } 基本操作： Adj_balance(T)

操作结果：创建平衡二叉树。 InsertAVL(T,search,taller)

初始条件：二叉树T已存在。 操作结果：增加新结点。 SetAVL(T,search,taller)

摘要

针对现实世界中许多关系复杂的数据，如人类社会的家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在的具有分支关系或层次特性的对象．如操作系统的文件构成、人工智能和算法分析的模型表示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客观世界问题，解决客观世界问题为主要任务的计算机领域中树型结构是信息的一种重要组织形式，树有着广泛应用。在树型结构的应用中又以二叉树最为常用。

二叉树是一种非常重要的非线性结构，所描述的数据有明显的层次关系，其中的每个元素只有一个前驱，二叉树是最为常用的数据结构，它的实际应用非常广泛，二叉树的遍历方式有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树。对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以表示成一株二叉树。反之

线性表实验报告+二叉树实验报告

实验报告

班级： 学号： 姓名： 日期：

1. 实验题目

编辑一个程序，用来演示线性表的建立、插入、删除等操作。

2. 需求分析

本演示程序在Microsoft Visual C++ 6.0环境下编写调试，完成线性表的生成、任意位置的插入、删除等。

（1）输入的形式和输入的范围：执行插入操作时，需要输入插入位置和元素的值；执行删除操作时，需要输入待删除元素的位置。在所有输入中，元素的值都是由整数、字符数组和字符数组组成的。

（2）输出的形式：在所有操作中都要求显示相关操作是否正确以及操作后线性表的内容。其中删除操作完成后，要显示删除后所剩的元素的值。

（3）程序所能达到的功能：完成线性表的生成、插入、删除操作。

3. 概要设计

（1）为了实现上述程序功能，需要定义线性表的数据结构。线性表单个元素的结构如图1.1所示。

图1.1 线性表元素的数据结构

（2）本程序包含6个函数： ①主函数main()。

②初始化线性表函数creat()。 ③插入元素函数insert()。 ④删除元素函数del()。

线性表实验报告+二叉树实验报告

各函数间的关系如图1.2所示

#include \#include \#define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status;

typedef char ElemType; typedef struct BiTNode {

ElemType data;

struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree;

Status CreateBiTree();

Status CreateBiTree(BiTree &T) // 算法6.4 {

// 按先序次序输入二叉树中结点的值（一个字符），’#’字符表示空树， // 构造二叉链表表示的二叉树T。 char ch;

scanf(\ if (ch=='#') T = NULL; else {

if (!(T = (BiTNode *)malloc(sizeof(BiTNode))))

第六章 习题

一、选择题

1、在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个 A 、4 B、5 C、6 D、 7

2、假定在一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（ ）个。

A、 15 B、16 C、17 Ｄ、47

3、假定一棵三叉树的结点数为50，则它的最小高度为（ ） A、 3 B、4 C、5 D、6

4、在一棵二叉树上第5层的结点数最多为（ ） A、8 B、 16 C、 15 D、32

5、用顺序存储方式将完全二叉树中的所有结点逐层存放在数组R[1..n]中，结点R[I]若有子树，则左子树是结点（ ）

A、R[2I+1] B、R[2I] C、R[I/2] D、R[2I-1] 6、在一棵具有k层的满三叉树中，结点总数为（ ） A、（3k-1）/2 B、3k-1 C、（3k-1）/3 D、3k

7、由带权为9，2，5，7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为（

山东工商学院

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

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）掌握树的各种术语，例如根、叶子、度、深度； （2）掌握二叉树的定义； （3）掌握二叉树的遍历方法； 理论课□ 讨论课□ 实验课□ 习题课□ 其他□ 课时 安排 授课题目：遍历二叉树 要求：（1）提高学生的认知能力； （2）培养学生自主学习和团结协作的能力； 教学重点及难点： 重点：（1）二叉树的定义； （2）二叉树的遍历方法。 难点：二叉树的遍历 教 学 基 本 内 容 遍历二叉树 一、二叉树的定义： 树基本定义： 树：包含N个结点的有穷集合；（N>0） 根：没有父母的结点； 叶子：没有孩子的结点或者度为0的结点； 度：某个结点孩子的个数； 深度：二叉树的层数 1.二叉树是每个结点的度都为2的有序树，它的特点是每个结点至多有两棵子树。 二叉树与树有区别：树至少应有一个结点，而二叉树可以为空；树的子树没有顺序，但如果二叉树的根结点只有一棵子树，必须明确区分它是左子树还是右子树，因为两者将构成不同形态的二叉树。因此，二叉树不是树的特例。它们是两种不同的数据结构。 二叉树有5种基本形态： (a) (b) (c)

实验报告

课程名：数据结构（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