实验六、树和二叉树的操作

一、实验目的

1．进一步掌握树的结构及非线性特点，递归特点和动态性。

2．进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法。

二、实验内容

二叉树的实现和运算

三、实验要求

1．用C++/C完成算法设计和程序设计并上机调试通过。

2．撰写实验报告，提供实验结果和数据。

3．分析算法，并简要给出算法设计小结和心得。

四、程序实现

#include＜iostream.h＞

#include＜stdlib.h＞

typedef char DataType;

typedef struct BitNode

{

DataType data;

struct BitNode *lchild,*rchild;

}*BitTree;

void BinTreeInit(BitTree &BT)//初始化二叉树，即把树根指针置空

{

BT=(BitTree)malloc(sizeof(BitNode));

BT-＞data=NULL;

cout＜＜"二叉树初始化成功!"＜＜endl;

}

int BinTreeCreat(BitTree &BT)//按先序次序建立一个二叉树

{

char ch;

cin＞＞ch;

if(ch=='#') BT=NULL;

else

{

if(!(BT=(BitTree)malloc(sizeof(BitNode))))

exit(0);

BT-＞data=ch;

BinTreeCreat(BT-＞lchild);

BinTreeCreat(BT-＞rchild);

}

…… …… 余下全文

 数据结构实验报告

指导教师     XX                                   实验时间：2010年11月1日

学院     计算机学院       专业   信息安全               

班级   XXXXXX       学号   XXXXX        姓名  XX      实验室  S331     

实验题目：二叉树操作

实验要求：

    采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历的操作，求所有叶子及结点总数的操作。

示例程序：

#include"stdio.h"

#include"string.h"

…… …… 余下全文

宁波工程学院电信学院计算机教研室

实验报告

一、实验目的

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)     

…… …… 余下全文

XX学院实验报告

五、实验总结和思考：（填写收获和体会，分析成功或失败的原因）

收获：只有通过不断练习，才能获取经验，避免下次犯同样的错误！

成功和失败： 在实验过程中，遇到了一些细节性的问题，不好寻找，导致结果错误。

结果：找到了问题所在，发现了一些平时不曾注意的问题。

附件：（源代码）

/*          说明

 1、树的元素类型为字符形；

 2、实现对二叉树的先序遍历操作；

 3、实现对二叉树的中序遍历操作；

4、实现对二叉树的后序遍历操作；

 5、求二叉树的深度；

 6、求二叉树的叶结点数；

 7、将二叉树中所有结点的左、右子树相互交换；

 */

#include "stdio.h"

#include "conio.h"

#define  OVERFLOW   -1

typedef char  telemtype;

typedef struct bitnode

{

    telemtype data;

    struct bitnode *lchild,*rchild;

    }bitnode,*bitree;

void createbitree(bitree *t)

{

    telemtype ch;

    scanf("%c",&ch);

    if(ch==' ') *t=NULL;

…… …… 余下全文

二叉树实验报告

问题描述

（1）问题描述：①用先序递归过程建立二叉树 (存储结构：二叉链表)。

输入数据按先序遍历所得序列输入，当某结点左子树或右子树为空时，输入‘*’号，如输入abc**d**e**得到的二叉树为：

                              

                         

                                     

                         

…… …… 余下全文

实验报告

姓名：       班级： 12南航网络    学号：           

…… …… 余下全文

一  实验题目

实现二叉树的基本操作的代码实现

二  实验目的

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

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

3、通过求二叉树的深度、度为2的结点数和叶子结点数等算法

三  实习要求

（1）认真阅读书上给出的算法

（2）编写程序并独立调试

四、给出二叉树的抽象数据类型

ADT BinaryTree{

//数据对象D：D是具有相同特性的数据元素的集合。
//数据关系R：
// 若D=Φ，则R=Φ，称BinaryTree为空二叉树；
// 若D≠Φ，则R={H}，H是如下二元关系；
// （1）在D中存在惟一的称为根的数据元素root，它在关系H下无前驱；
// （2）若D-{root}≠Φ，则存在D-{root}={D1,Dr}，且D1∩Dr =Φ；
// （3）若D1≠Φ，则D1中存在惟一的元素x1，<root,x1>∈H，且存在D1上的关系H1 ?H；若Dr≠Φ，则Dr中存在惟一的元素xr，<root,xr>∈H，且存在上的关系Hr ?H；H={<root,x1>,<root,xr>,H1,Hr}；
// （4）(D1,{H1})是一棵符合本定义的二叉树，称为根的左子树；(Dr,{Hr})是一棵符合本定义的二叉树，称为根的右子树。

//基本操作：
CreateBiTree( &T, definition )
// 初始条件：definition给出二叉树T的定义。
// 操作结果：按definiton构造二叉树T。

BiTreeDepth( T )
// 初始条件：二叉树T存在。
// 操作结果：返回T的深度。

PreOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。

…… …… 余下全文