二叉树应用

二叉树应用 数据结构实验报告 二叉树的应用 一、实验目的 实现二叉排序树的应用。 二、实验 内容 财务内部控制制度的内容财务内部控制制度的内容人员招聘与配置的内容项目成本控制的内容消防安全演练内容 (问题) 设计一个程序，实现二叉排序树的应用。基本要求: (1)从空树开始，通过插入，建立一棵二叉排序树; (2)检验所建立的二叉树是否是二叉排序树; (3)实现二叉排序树的删除。 三、算法描述 (给出自然语言描述的算法) 1.建立一棵空树，把数据元素插入树中; 2.检验这棵树是不是二叉排序树; 3.输入一个关键字，删除该数据元素。 四、详细设计(画流程图) 建立空树 否 该树中是否有要不插入 插入的数据元素 是 插入并检测数据元素 五、程序代码 #include "stdio.h" #include "stdlib.h" #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define FALSE 0 #define TRUE 1 typedef int Status; typedef struct ElemType{ int key; char name[15]; }ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; FILE *fp; Status SearchBST(BiTree T,int key,BiTree f,BiTree &p); Status InsertBST(BiTree &T,ElemType e); Status PreOrderTraverse(BiTree T,Status(*visit)(ElemType)); Status Show(ElemType e); Status InspectBST(BiTree T); Status DeleteBST(BiTree &T,int key); Status Delete(BiTree &p); main(){ BiTree T=NULL; ElemType e; int i,key; if((fp=fopen("data.txt","read"))==NULL){ printf("Can't open file!\n"); exit(0); } for(i=0;i<16;i++){ fscanf(fp,"%d%s\n",&e.key,e.name); InsertBST(T,e); } fclose(fp); printf("二叉排序树建立成功。\n"); if(InspectBST(T))printf("此二叉树是二叉排序树。\n"); else return FALSE; printf("先序遍历序列是:\n"); if(PreOrderTraverse(T,Show))printf("\n"); for(i=0;i<3;i++){ printf("输入要删除数据元素的关键字:"); scanf("%d",&key); if(DeleteBST(T,key)){ printf("删除该数据元素后的先序遍历是:\n"); PreOrderTraverse(T,Show); printf("删除成功。\n"); } else printf("二叉树中没有此数据元素，删除失败。\n"); } return TRUE; } Status SearchBST(BiTree T,int key,BiTree f,BiTree &p){ if(!T){ //查找不成功 p=f; return FALSE; } else if(EQ(key,T->data.key)){ //查找成功 p=T; return TRUE; } else if LT(key,T->data.key)return SearchBST(T->lchild,key,T,p); //在左子树中继续查找 else return SearchBST(T->rchild,key,T,p); //在左子树中继续查找 } Status InsertBST(BiTree &T,ElemType e){ BiTree p,s; if(!SearchBST(T,e.key,NULL,p)){ //查找不成功 s=(BiTree)malloc(sizeof(BiTNode)); s->data=e; s->lchild=s->rchild=NULL; if(!p)T=s; //被插结点*s为新的根结点 else if LT(e.key,p->data.key)p->lchild=s; //被插结点*s为左孩子 else p->rchild=s; //被插结点*s为左孩子 return TRUE; } else return FALSE; //树中已有关键字相同的结点，不再插入 } Status DeleteBST(BiTree &T,int key){ if(!T)return FALSE; //不存在关键字等于key的数据元素 else{ if(EQ(key,T->data.key))return Delete(T); //找到关键字key的数据元素 else if(LT(key,T->data.key))return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key); } } Status Delete(BiTree &p){ BiTree q,s; if(!p->rchild){ //右子树空则只需重接它的左子树 q=p; p=p->lchild; free(q); } else if(!p->lchild){ //只需重接它的右子树 q=p; p=p->rchild; free(q); } else{ //左右子树都不空 q=p; s=p->lchild; while(s->rchild){ //转左，然后向右到尽头 q=s; s=s->rchild; } p->data=s->data; //s指向被删除接点的“前驱” if(q!=p)q->rchild=s->lchild; //重接*q的右子树 else q->lchild=s->lchild; //重接*q的左子树 Delete(s); } return TRUE; } Status InspectBST(BiTree T){ if(!T)return TRUE; if(T->lchild==NULL && T->rchild==NULL)return TRUE; //没有左右子树 if((T->lchild!=NULL && T->lchild->data.key>T->data.key) || (T->rchild!=NULL && T->data.key>T->rchild->data.key)) return FALSE; return InspectBST(T->lchild) && InspectBST(T->rchild); } Status PreOrderTraverse(BiTree T,Status(*visit)(ElemType)){ if(T){ if((*visit)(T->data)) if(PreOrderTraverse(T->lchild,visit)) if(PreOrderTraverse(T->rchild,visit))return TRUE; return FALSE; } else return TRUE; } Status Show(ElemType e){ printf("%d %s\n",e.key,e.name); return TRUE; } 六、测试和结果 (给出测试用例，以及测试结果)