1、 数据结构及其应用数据结构及其应用 一、问题描述一、问题描述 二叉树是一种常见的数据结构， 在实际中应用十分广泛。 二叉树有顺序和链式两种存储 结构，可以运用递归和非递归设计算法，能够求解节点在二叉树中的层次数等问题。在实际 应用中，要求以同学录为例完成系统的设计与管理。 二、基本要求二、基本要求 1、选择合适的存储结构，完成二叉树的建立。最好采用顺序和链式两种方法。 2、在顺序二叉树中求解节点所在层次数。 3、在链式二叉树中求解节点所在层次数。 4、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。 三、测试数据三、测试数据 1、分别以顺序和链式存储测试图示二叉树中节点 E
2、 所在层次： 2、同学录的测试数据： “赵一“,“1979-01-01“,“15811111111“,“0807011001“ “钱二“,“1980-02-02“,“15822222222“,“0807011002“ “孙三“,“1981-03-03“,“15833333333“,“0807011003“ “李四“,“1982-04-04“,“15844444444“,“0807011004“ 在上表的的基础上，测试表的建立，以及记录的新增、修改、删除等。 四、算法思想四、算法思想 1、在顺序二叉树下求节点所在层次数 本题中顺序二叉树按照满二叉树的原则建立，空节点存“0” 。故节点所在层次 c
3、ount 与节点下标 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 和rear是数组queue中当前正
4、在访问的节点的下标以及可插入节点的下标，而flag起到标 志作用用来表明是否要增加当前的层次数 n。 算法开始时，首先判断树是否为空，若为空树退出程序；若树不为空，则先判断根节点 的值是否与要查找节点的值相等，若相等则返回 n，否则将当前层次 n 加 1，并将根节点的 左孩子、右孩子以及根节点本身插入到数组 queue 中。可能，有人会问为什么还要将根节 点插入到数组 queue 中？这里，将根节点插入到数组 queue 中的目的是，当 queuefront 保存的是根节点的指针时，二叉树的一层节点遍历结束了，需要将当前层次数 n 加 1 并让 queuerear保存根节点的指针。 算法的核心部分就是while循环里面的内容，首先让标志flag值为0,如果queuefront 不为空且 queuefront-data 的值等于要查找的值 c，程序结束返回 n 即可；若 queuefront的值是指向根节点的指针，表明当前层次上的所有节点都已经访问过了，要 访问下一个层次的节点了，故要把 n 加 1 并让 flag 值为 1 以表明在数组的插入位置 qu
