二叉树及其应用(算法与数据结构课程设计)

二叉树及其应用

一、问题描述

二叉树是一种常见的数据结构,在实际中应用十分广泛。二叉树有顺序和链式两种存储结构,可以运用递归和非递归设计算法,能够求解节点在二叉树中的层次数等问题。在实际应用中,要求以同学录为例完成系统的设计与管理。

二、基本要求

1、选择合适的存储结构,完成二叉树的建立。最好采用顺序和链式两种方法。 2、在顺序二叉树中求解节点所在层次数。 3、在链式二叉树中求解节点所在层次数。

4、以同学录为例,利用二叉树存储结构,实现建立、查找、新增、删除等功能。

三、测试数据

1、分别以顺序和链式存储测试图示二叉树中节点E所在层次:

2、同学录的测试数据:

\赵一\ \钱二\ \孙三\ \李四\

在上表的的基础上,测试表的建立,以及记录的新增、修改、删除等。

四、算法思想

1、在顺序二叉树下求节点所在层次数

本题中顺序二叉树按照满二叉树的原则建立,空节点存“0”。故节点所在层次count与节点下标m有如下关系:

1)初始层次数count=1,当m=0时,所查节点不存在 2)当m非0时,令m=m/2,count加一

3)m不为1时,返回层次数count;m为1时,重复步骤2) 2、在链式二叉树下求节点所在层次数

算法要用非递归算法求解二叉树中给定节点的深度,为实现层次非递归求解,必须借用数据结构保存将要访问的节点,在函数CengciTree(BiTreeLink T,char c)中用数组queue实现此功能。具体编程时,用变量n保存当前访问的节点的层次数目并初始化为1,front

wilyes11收集 博客(与学习无关):http://blog.sina.com.cn/u/1810231802

和rear是数组queue中当前正在访问的节点的下标以及可插入节点的下标,而flag起到标志作用用来表明是否要增加当前的层次数n。

算法开始时,首先判断树是否为空,若为空树退出程序;若树不为空,则先判断根节点的值是否与要查找节点的值相等,若相等则返回n,否则将当前层次n加1,并将根节点的左孩子、右孩子以及根节点本身插入到数组queue中。可能,有人会问为什么还要将根节点插入到数组queue中?这里,将根节点插入到数组queue中的目的是,当queue[front]保存的是根节点的指针时,二叉树的一层节点遍历结束了,需要将当前层次数n加1并让queue[rear]保存根节点的指针。

算法的核心部分就是while循环里面的内容,首先让标志flag值为0,如果queue[front]不为空且queue[front]->data的值等于要查找的值c,程序结束返回n即可;若queue[front]的值是指向根节点的指针,表明当前层次上的所有节点都已经访问过了,要访问下一个层次的节点了,故要把n加1并让flag值为1以表明在数组的插入位置queue[rear]需要赋值为跟节点的指针;如果,均不是上述情况,则将queue[front]的左孩子、右孩子都放到数组queue中,并将front指向下一个元素。重复上述循环,直到找到了要查找的值,或者遍历了所有的节点。 3、同学录的实现

本题的一个实际应用是实现同学录,我们采用二叉树存储结构,利用预置数组建立二叉树;先序方式遍历二叉树并输出;递归算法实现对同学录的查找;基于查找实现对同学录的修改和新增成员;求所要操作节点的父亲节点,从而顺利的编写对同学录的删除操作。

五、模块划分:

1、在顺序二叉树下求节点所在层次数

(1)void Creattree()其功能是建立顺序二叉树; (2)void Cengcitree()其功能是求节点层次 2、在链式二叉树下求节点所在层次数

(1

>>鐏炴洖绱戦崗銊︽瀮<<
12@gma联系客服:779662525#qq.com(#替换为@)