数据结构二叉树实践报告

编辑:阿文时间:2020-06-12 15:07:06
数据结构二叉树实践报告,熟练掌握二叉树的建立方法,输出二叉树的三种遍历序列,先按遍历顺序输入生成树,并计算出输出树的深度叶节点数汇点数,并计算出输出树的深度叶节点数汇点数。

实验报告

计算机科学与技术学院

实验教学中心

2017年11月17日

实验项目名称:二叉树的建立与遍历

一、实验目的:

(1)熟练掌握二叉树的建立方法;

(2)熟练掌握二叉树的遍历算法;

(3)掌握二叉树的应用算法。

二、实验内容:

(1)编写算法建立一棵二叉树的二叉链表;

(2)输出二叉树的三种遍历序列,包括递归算法、非递归算法;

(3)编写算法统计二叉树结点数、叶子数、深度。

三、实验结果分析

四、实验操作步骤

先按遍历顺序输入生成树,用输入替换空节点,递归生成树。

输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。

并计算出输出树的深度、叶节点数、汇点数

然后根据序列遍历序列输入建立完整的二叉树,采用非递归树。

输出结果为该树按先序遍历、中序遍历、后序遍历的顺序序列。

并计算出输出树的深度、叶节点数、汇点数

五、源**

#include

#include

#include

#include

using namespace std;

//二叉树定义

typedef char elementtype;

typedef struct bitreenode

bitreenode,* bitree;

//递归的建立一棵二叉树

//以二叉树为输入的序列

void createbitree(bitree &t)

else

}void creatbitree_2(bitree &rt,int n)

bitreenode *node=new bitreenode;

node->data=tmp[0];

node->rchild=null;

node->lchild=null;

for(int j=num-2; j>0; j--)

if(a[j])t=t->rchild;

else t=t->lchild;

if(a[0])t->rchild=node;

else t->lchild=node;

}}int nodenum(bitreenode* root)//二叉树节点数目

//递归地销毁二叉树

void destroybitree(bitree &t)

}//递归预序遍历二叉树

void preordertraverse(const bitree &t)

}//递归中阶遍历二叉树

void inordertraverse(const bitree &t)

}//递归后序遍历二叉树

void postordertraverse(const bitree &t)

}//递归地查找树的深度

int depthofbitree(const bitree &t)

//递归查找二叉树的叶结点数

int leafcountofbitree(const bitree &t)

int main(int argc, char *argv)

数据结构二叉树实践报告(二)

一、需求分析:

编写一段程序,对二叉树进行复合操作,包括创建一棵二叉树,显示二叉树的树型结构,对创建的二叉树进行先根、中根、后根三种方式进行遍历,并且打印出叶子结点,并且可以随时删除我们创建的二叉树,然后用循环语句将上述的操作封装起来,使之能够进行可重复、连续的操作。输入为a-z或者是a-z之间的字符,用‘@’字符作为结束当前结点的标识符。

二、概要设计:

要在此程序中使用的数据类型

struct bintreenode

;然后定义我们需要的指针类型

typedef struct bintreenode*pbintreenode; /* 定义指向二叉树结点的指针类型*/

typedef pbintreenode*pbintree; /*定义指向树型结点的指针类型*/

程序所需的自定义函数

一。创建二叉树根节点

pbintree create_bintreeroot(void)

2。创建二叉树的节点

pbintreenode create_bintreenode(void)

3.创建一棵二叉树

pbintreenode create_bintree(void)

四。用第一根法遍历二叉树

void preorder(pbintreenode pbnode)

5个。用中根法遍历二叉树

void inorder(pbintreenode pbnode)

6.使用backroot方法遍历二叉树

void postorder(pbintreenode pbnode)

7号。打印出我们创建的二叉树的树结构

void outputtree(pbintreenode pbnode,int totalspace)

8个。打印出二叉树的叶节点

void leaves(pbintreenode pbnode)

9。释放我们申请的所有结点空间

void freeallnodes(pbintreenode pbnode)

10个。判断是否输入合格字符

int isalphabet(char i)

三、详细设计:

1. pbintreenode create_bintreenode(void)

我们定义一个指向二叉树结点类型的指针pbintreenode,然后,申请一个二叉树结点大小的空间,对左右子结点赋为空。

2。创建二叉树根节点

定义一个指向二叉树结点的指针的指针即:bintreenode ** pbtree, 或者是:pbintreenode *pbtree;用于存放树的根结点,同时,将我们创建的二叉树的地址传给它即:

*pbtree=create_bintree();

3. 创建一棵二叉树

首先我们定义一个datatype类型的变量i,用于存放我们输入的字符(即作为缓冲区),并用scanf函数去接收它,由于使用scanf函数时,会出现吸收我们输入的回车字符,并将会车作为接收的字符的情况发生,为了避免这种情况,我们用函数fflush(stdin)将缓冲区的字符全部冲掉,然后再吸收我们输入的字符,就可以完全避免此类问题的发生。我们定义我们输入的字符是从a-z或者是a-z,用字符@为我们结束当前结点左或者右结点的字符,然后递归调用左右子树,此时我们将一棵二叉树全整的创建出来了。

四。用第一根法遍历二叉树

首先访问根结点,打印出其中的信息,然后递归调用左子树和右子树。

5个。用中根法遍历二叉树

首先递归调用左子树,打印出其中的信息,打印出根结点信息,然后递归调用右子树,打印出其中的信息。

6.使用backroot方法遍历二叉树

首先,递归地调用左子树来打印内容,然后递归地调用右子树来打印内容,然后是根结点的内容。

7号。打印出我们创建的二叉树的树结构

先递归调用右子树,如果结点不为空的话,空格数加5,如果为空的话,就打印出右子树的内容,然后递归调用左子树。

8个。打印出二叉树的叶节点

如果当前结点的左右子树都为空的话,就打印出此结点的信息,如果左子树不为空的话,递归调用左子树,如果右子树不为空的话,递归调用右子树。

9。释放我们申请的所有结点空间

如果当前的左子树不为空,则遍历左子树,如果右子树不为空的话,则遍历右子树,如果都不位空的话,分别调用左右子树,如果左右都为空的话,就释放左右结点空间,并将当前结点置为空。

10.主函数的安排:

先创建好我们要的二叉树,之后,我们就可以对此而二树进行多种操作,我们定义了6种集合操作,并对用户输入的信息进行检测,正确的提示出错信息,如果选择的是我们定义的操作之一的话,对应的我们设置出不同的case语句。如果我们选择的是释放所有的结点空间的话,我们需要屏蔽掉所有的菜单信息,提示用户重新创建一棵二叉树,并对它进行重新操作。

如果我们选择退出,但是没有选择释放掉所有的节点空间时,我们需要考虑到此类的情形,应调用void freeallnodes(pbintreenode pbnode)自动的释放掉所有的结点空间,正常的退出。

四、用户使用说明:

当用户尚未创建二叉树时,系统会提示用户输入数据:

please input char to the binatree, @ to exit current node:please input a char:

这时用户用键盘输入,每输入一个字符回车一次,输入为a-z或者是a-z之间的字符,用‘@’字符作为结束当前结点的标识符

当用户创建二叉树时,将显示“控制”菜单:

please choose the mode you want to operate with the binatree:

1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:

此时,用户可以选择操作:1。自动打印出树结构。先遍历根;3。穿过中根;4。稍后遍历根

5个。打印叶结点6。释放所有结点空间0。出口

五、测试结果:

一。测试完整二叉树的情况:

输入(每输入一个字符回车一次):a b c @ @ d @ @ e f @ @ g @ @

自动打印出树型结构:

display the binatree data directly:ge

fadb

c三种遍历方法和叶结点测试如下:

先根:data in preorder:

a b c d e f g

中根:按顺序排列的数据:

c b d a f e g

后根:data in postorder:

c d b f g e a

打印叶子结点:

leaves:

c d f g

释放所有结点空间:

free all nodes:

all node have been freed successfully.

自动提示创建新的二叉树:

now creating a new binatree...

please input char to the binatree, @ to exit current node:

please input a char:

测试不完整的二叉树的情况

输入(每个字符输入一次):a b c d

自动打印出树型结构:

abc d

三种遍历方法和叶结点测试如下:

先根:data in preorder:

a b c d

中根:按顺序排列的数据:

d c b a

后根:data in postorder:

d c b a

打印叶子结点:

leaves:d

释放所有结点空间:

free all nodes:

all node have been freed successfully.

自动提示创建新的二叉树:

now creating a new binatree...

please input char to the binatree, @ to exit current node:

please input a char:

如果要结束此操作并退出此程序,可以输入0,程序将自动释放所有结点空间:

please choose the mode you want to operate with the binatree:

1.display 2.preorder 3.inorder 4.postorder 5.leaves 6.free nodes 0 to exit:0

dealing with the last job, to free all nodes

all node have been freed successfully

六、附录:

#include

#include

#include

#define null 0

#define datatype char

typedef struct bintreenode*pbintreenode;

typedef pbintreenode*pbintree;

struct bintreenode

;pbintreenode create_bintree(void);

pbintree create_bintreeroot(void)

{pbintree pbtree;

pbtree=(pbintree)malloc(sizeof(struct bintreenode));