二叉树及其应用
一、问题描述
二叉树是一种常见的数据结构，在实际中应用十分广泛。二叉树有顺序和链式两种存储结构，可以运用递归和非递归设计算法，能够求解节点在二叉树中的层次数等问题。在实际应用中，要求以同学录为例完成系统的设计与管理。
二、基本要求
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）int CreateBiTree(BiTreeLink *T)其功能是建立二叉树；
（2）void PreOrderTraverse(BiTreeLink T) 其功能是先序遍历二叉树； （3）int CengciTree(BiTreeLink T,char c) 其功能是求层次数 （1）int n=0,front=0,rear=0,flag;初始化队列； （2）(front+1)%MAXSIZE!=rear判断队列不满。
3、以同学录为例，利用二叉树存储结构，实现建立、查找、新增、删除等功能。 （1）void CreateBiTree(DataType *items,BiTree *T)其功能是建立同学录 （2）void PreOrderTraverse(BiTree T)
（3）PBTNode SearchTree(BiTree T,char *ch) （4）void ModifyTree(BiTree T) （5）void DeleteTree(BiTree T)
4、main()主函数，功能是调要相关函数实现问题的求解。
六、数据结构：
1、二叉树的抽象数据类型结构定义： typedef struct Node { TElemType data;
struct Node *lchild,*rchild; } BiTNode, *BiTreeLink;
wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802
2、同学录节点信息： typedef struct Info{
char name[20]; //姓名 char date[11]; //生日 char phone[12]; //电话 char StudentNum[11];//学号 }DataType;
3、同学录数据存储结构： typedef struct Node { DataType data;
struct Node *left,*right; }BTNode, *PBTNode,*BiTree;
七、源程序：
1、在顺序二叉树下求节点所在层次数 #define maxlen 100 #include\typedef struct node { char data;
} Bitree[maxlen]; int N; Bitree T; /*建立二叉树*/ void Creattree() { int i; char c;
printf(\请输入结点数目(包括空结点)：\ scanf(\
printf(\请输入结点(空结点为0):\ for(i=1;i<=N;i++) {
scanf(\ T[i].data=c; } }
/*求二叉树节点所在层次*/ void Cengcitree() {
int i,m=0,count=1; char c; printf(\请输入某一结点：\ scanf(\ i=1;
while(i<=N) {
if(T[i].data==c){m=i; break;}
wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802
i++; }
if (m==0)
printf(\节点不存在\ while(m!=1) {
m=m/2; count++; }
printf(\节点所在层次:%d\\n\}
/*主函数*/ void main() {
Creattree(); Cengcitree();}
2、在链式二叉树下求节点所在层次数 #include \#include
typedef char TElemType;
/* 二叉链树的类型定义*/ typedef struct BiTNode { TElemType data;
struct BiTNode *lchild,*rchild; } BiTNode, *BiTreeLink;
/*先序建立二叉树*/
int CreateBiTree(BiTreeLink *T) { char ch;
scanf(\ if (ch==' ') *T=NULL; else
{ *T=(BiTreeLink)malloc(sizeof(BiTNode));
if (!(*T)) return 0; /* 未分配到空间错误返回*/ (*T)->data=ch;
CreateBiTree(&(*T)->lchild); CreateBiTree(&(*T)->rchild); } return 1; }
wilyes11收集 博客(与学习无关)：http://blog.sina.com.cn/u/1810231802