二叉树应用.doc

数据结构实验报告二叉树的应用一、实验目的实现二叉排序树的应用。二、实验内容（问题）设计一个程序，实现二叉排序树的应用。基本要求：（1）从空树开始，通过插入，建立一棵二叉排序树；（2）检验所建立的二叉树是否是二叉排序树；（3）实现二叉排序树的删除。三、算法描述 （给出自然语言描述的算法）1.建立一棵空树，把数据元素插入树中；2.检验这棵树是不是二叉排序树；3.输入一个关键字，删除该数据元素。四、详细设计（画流程图）建立空树该树中是否有要插入的数据元素不插入插入输入要删除元素的关键字判断i是否大于13（i=0;i13;i+）检验该树是不是二叉排序树该数据元素在二叉排序树中是否存在删除数据元素删除失败插入并检测数据元素是否是否结束否是否是五、程序代码#include stdio.h#include stdlib.h#define EQ(a,b) (a)=(b)#define LT(a,b) (a)(b)#define FALSE 0#define TRUE 1typedef int Status;typedef struct ElemTypeint key;char name15;ElemType;typedef struct BiTNodeElemType 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(Cant open file!n); exit(0);for(i=0;i16;i+)fscanf(fp,%d%sn,&e.key,);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;idata.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的数据元素elseif(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.keyT-data.key) | (T-rchild!=NULL & T-data.keyT-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-rchil