GJQ实验3-排序二叉树的建立和查找.doc

软件技术基础实验指导书实验三 排序二叉树的建立和查找一、实验题目：排序二叉树的建立和查找二、实验目的：掌握非线性数据结构的描述方法三、实验内容：（1）附录中是用链式结构实现二叉树的建立、查询和打印的源程序。请将他们输入计算机，编译、连接并运行。（2）读懂上述程序，并编写删除一个结点的子函数。四、实验报告要求： 软件技术基础实验报告实验名称：排序二叉树的建立和查找班级： 学号： 姓名：实验目的：掌握非线性数据结构的描述方法实验内容：（1）附录中是用链式结构实现二叉树的建立、查询和打印的源程序。请将他们输入计算机，编译、连接并运行。（2）读懂上述程序，并编写删除一个结点的子函数。实验原理：写出删除排序二叉树中一个结点的算法（形式语言）。实验步骤：写出调试、查找程序中问题的思路和步骤。实验结果：写出删除排序二叉树中一个结点的子程序。附录：二叉树的建立、查询、打印和遍历的源程序：#include#include/*/define the structure of an element of a tree/*struct tree char info; struct tree *left,*right; ;/*/explanation the functions /*struct tree *create_btree(struct tree *root,struct tree *r,char info);struct tree *search_btree(struct tree *root,char key);void print_btree(struct tree *r,int l);void PreOrder(struct tree *T); /先序递归遍历二叉树void InOrder(struct tree *T); /中序递归遍历二叉树void PostOrder(struct tree *T); /*/ the main function /*void main() char s100, c ; struct tree *root=0, *p; printf(Input a letter for Creating the Binary_Tree ( Directly press to stop ):n); do printf(Input a letter: ); gets(s);if (!root)root=create_btree(root,root,*s);elsecreate_btree(root,root,*s); while (*s) ;while ( c!=!)print_btree(root,0);printf(Enter a character to find( ! to stop ):);scanf(%s,&c);printf(n);p=search_btree(root,c); printf(n);printf(n先序遍历结果：); PreOrder(root); /先序递归遍历二叉树 printf(n中序遍历结果：); InOrder(root); printf(n后序遍历结果：); /中序递归遍历二叉树 PostOrder(root); printf(n); /* Btree.C 结束 */ struct tree *create_btree(struct tree *root,struct tree *r,char info) if (r =0 ) r=new (struct tree);if ( r = 0) printf(Out of memoryn); return 0 ; r-left= 0; r-right=0; r-info=info;if (root) if(infoinfo) root - left=r;else root-right=r;else r-right=0; r-left = 0; return r; if (info info)create_btree(r,r-left,info);if(info=r-info)create_btree(r,r-right,info); /* create_btree(root,r,info) */*/tree *search_btree(struct tree *root,char key)/*struct tree *search_btree(struct tree *p,char key) struct tree *root;root=p;if (!root) printf(Empty btreen); return root; while(root-info!=key) if(keyinfo) root=root-left;elseroot=root-right;if(root=0) printf(Search Failuren); return 0; /* while(root-info!=key) */if (root !=0)printf(Successful searchn key=%cn,root-info);return root ; /* *search_btree(root,key) */*/ print_btree /*void print_btree(struct tree *r,int l) int i;if (r = 0) return ;print_btree(r-left,l+1);for(i=0;iinfo);print_btree(r-right,l+1); void PreOrder(struct tree *T) if(T) printf(%c,T-info); /访问结点 PreOrder(T-left); /遍历左子树 PreOrder(T-right); /遍历右子树 void InOrder(struct tree *T)if(T) InOrder(T-left); /遍历左子树 printf(%c,T-info); /访问结点 InOrder