《二叉树应用》由会员分享，可在线阅读，更多相关《二叉树应用（6页珍藏版）》请在金锄头文库上搜索。
1、数据结构实验报告二叉树的应用一、实验目的实现二叉排序树的应用。二、实验内容（问题）设计一个程序，实现二叉排序树的应用。基本要求：（1）从空树开始，通过插入，建立一棵二叉排序树；（2）检验所建立的二叉树是否是二叉排序树；（3）实现二叉排序树的删除。三、算法描述 （给出自然语言描述的算法）1.建立一棵空树，把数据元素插入树中；2.检验这棵树是不是二叉排序树；3.输入一个关键字，删除该数据元素。四、详细设计（画流程图）建立空树该树中是否有要插入的数据元素不插入插入输入要删除元素的关键字判断i是否大于13（i=0;i13;i+）检验该树是不是二叉排序树该数据元素在二叉排序树中是否存在删除数据元素删除失
2、败插入并检测数据元素是否是否结束否是否是五、程序代码#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;Stat
3、us 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,k
4、ey;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,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;idata.key) /查找成功p=T;
5、 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; /
6、被插结点*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)retur
7、n 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指向被删除接
8、点的“前驱”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) retu
9、rn 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 %sn,e.key,e.name);return TRUE;六、测试和结果 （给出测试用例，以及测试结果）差距大，市场体系不完善，缺乏集聚效应等问题，同时充分考虑到该地周围已形成成熟建材商圈的商业价值，因地制宜的进行家居建材广场的建设。通过合理布局、优化环境、提升服务，该项目必将切实发挥商业区在引导消费、拉动经济增长方面的作用，促进该县经济和社会又好又快发展。
